257752026-03-01 23:02:42abcdEgyirányú egyensúlycpp17Runtime error 40/5046ms3892 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int maxn=50001,maxm=200001;
vector<array<int,3>> adj[maxn];
int dir[maxm],cnt[maxn];

void euler(int start){
    stack<int> st;
    st.push(start);
    while(!st.empty()){
        int v=st.top();
        bool found=false;
        while(cnt[v]<adj[v].size()){
            auto [to,i,d]=adj[v][cnt[v]++];
            if(dir[i]!=0)continue;
            dir[i]=d;
            found=true;
            st.push(to);
            break;
        }
        if(!found)st.pop();
    }
}

int main(){
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        adj[a].pb({b,i,1});
        adj[b].pb({a,i,2});
    }
    vector<int> odds;
    for(int i=1;i<=n;i++)if(adj[i].size()&1)odds.pb(i);
    for(int i=0;i<odds.size()-1;i+=2){
        adj[odds[i]].pb({odds[i+1],m+i+1,1});
        adj[odds[i+1]].pb({odds[i],m+i+1,2});
    }
    for(int v=1;v<=n;v++){
        if(cnt[v]<adj[v].size())euler(v);
    }
    cout<<odds.size()<<'\n';
    for(int i=0;i<m;i++){
        if(dir[i]==1)cout<<"<- ";
        else cout<<"-> ";
    }
    cout<<'\n';
}
SubtaskSumTestVerdictTimeMemory
base40/50
1Accepted0/02ms1780 KiB
2Accepted0/034ms3380 KiB
3Accepted2/22ms1780 KiB
4Runtime error0/22ms1536 KiB
5Accepted2/22ms1332 KiB
6Accepted2/22ms1332 KiB
7Runtime error0/22ms1588 KiB
8Accepted2/23ms1780 KiB
9Accepted2/22ms1588 KiB
10Accepted2/22ms1596 KiB
11Accepted2/23ms1588 KiB
12Accepted2/23ms1424 KiB
13Accepted3/38ms1844 KiB
14Accepted3/318ms2548 KiB
15Accepted3/320ms2612 KiB
16Runtime error0/320ms2776 KiB
17Accepted3/312ms2100 KiB
18Runtime error0/321ms2628 KiB
19Accepted3/327ms2916 KiB
20Accepted3/337ms3380 KiB
21Accepted3/339ms3636 KiB
22Accepted3/346ms3892 KiB