32932023-02-24 12:11:31sztomiEgyirányú egyensúlycpp11Hibás válasz 13/5023ms9232 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int n, m;
vector<int> kifok;
vector<int> befok;
vector<pii> elek;
vector<vector<pii>> graf;
vector<bool> fordult;
vector<bool> volt;

void megold(int akt, bool& tobb_be){
    volt[akt] = true;
    if(graf[akt].size() % 2){
        if(tobb_be){
            befok[akt] = graf[akt].size() / 2;
            kifok[akt] = graf[akt].size() - befok[akt];
        }
        else{
            kifok[akt] = graf[akt].size() / 2;
            befok[akt] = graf[akt].size() - kifok[akt];
        }
        tobb_be = !tobb_be;
    }
    else{
        kifok[akt] = befok[akt] = graf[akt].size() / 2;
    }

    for(auto kov : graf[akt]){
        if(volt[kov.first]) continue;
        megold(kov.first, tobb_be);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    int a, b;
    kifok.assign(n+1, 0);
    befok.assign(n+1, 0);
    elek.resize(m);
    graf.assign(n+1, vector<pii>());
    fordult.assign(m, false);
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        graf[a].push_back({b, i});
        graf[b].push_back({a, i});
        kifok[a]++;
        befok[b]++;
        elek[i] = {a, b};
    }

    int ossz = 0;
    for(int i = 1; i <= n; i++){
        ossz += ((befok[i]+kifok[i]) % 2);
    }

    volt.assign(n+1, false);
    for(int i = 1; i <= n; i++){
        if(volt[i]) continue;
        bool tobb_be = false;
        megold(i, tobb_be);
    }

    for(int i = 0; i < m; i++){
        a = elek[i].first;
        b = elek[i].second;
        if(kifok[a] == 0){
            kifok[b]--;
            befok[a]--;
            fordult[i] = true;
        }
        else if(kifok[b] == 0){
            kifok[a]--;
            befok[b]--;
            fordult[i] = false;
        }
        else{
            kifok[a]--;
            befok[b]--;
            fordult[i] = false;
        }
    }

    cout << ossz << "\n";
    for(int i = 0; i < m; i++){
        cout << (fordult[i] ? "<- " : "-> ");
    }
    cout << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base13/50
1Hibás válasz0/03ms1700 KiB
2Hibás válasz0/017ms5808 KiB
3Elfogadva2/23ms2080 KiB
4Elfogadva2/23ms2284 KiB
5Elfogadva2/23ms2372 KiB
6Hibás válasz0/23ms2368 KiB
7Hibás válasz0/23ms2636 KiB
8Hibás válasz0/23ms2908 KiB
9Elfogadva2/23ms2928 KiB
10Hibás válasz0/23ms2952 KiB
11Elfogadva2/23ms3240 KiB
12Hibás válasz0/23ms3096 KiB
13Hibás válasz0/37ms4084 KiB
14Hibás válasz0/310ms5872 KiB
15Elfogadva3/313ms6296 KiB
16Hibás válasz0/312ms5896 KiB
17Hibás válasz0/38ms5620 KiB
18Hibás válasz0/313ms5872 KiB
19Hibás válasz0/314ms6152 KiB
20Hibás válasz0/317ms8184 KiB
21Hibás válasz0/319ms8020 KiB
22Hibás válasz0/323ms9232 KiB