257792026-03-01 23:16:05abcdEgyirányú egyensúlycpp17Elfogadva 50/5046ms3032 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int maxn=20001,maxm=500001;
vector<array<int,3>> adj[maxn];
int dir[maxm*2],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]<(int)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<(int)odds.size()-1;i+=2){
        adj[odds[i]].pb({odds[i+1],m+i,1});
        adj[odds[i+1]].pb({odds[i],m+i,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';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms820 KiB
2Elfogadva0/034ms2864 KiB
3Elfogadva2/21ms820 KiB
4Elfogadva2/21ms820 KiB
5Elfogadva2/21ms820 KiB
6Elfogadva2/21ms820 KiB
7Elfogadva2/21ms820 KiB
8Elfogadva2/22ms820 KiB
9Elfogadva2/21ms820 KiB
10Elfogadva2/22ms948 KiB
11Elfogadva2/23ms820 KiB
12Elfogadva2/23ms832 KiB
13Elfogadva3/39ms1332 KiB
14Elfogadva3/317ms1636 KiB
15Elfogadva3/319ms2100 KiB
16Elfogadva3/324ms2156 KiB
17Elfogadva3/310ms1436 KiB
18Elfogadva3/324ms2100 KiB
19Elfogadva3/327ms2160 KiB
20Elfogadva3/335ms2868 KiB
21Elfogadva3/341ms2944 KiB
22Elfogadva3/346ms3032 KiB