3293 2023. 02. 24 12:11:31 sztomi Egyirányú egyensúly cpp11 Hibás válasz 13/50 23ms 9232 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 Összpont Teszt Verdikt Idő Memória
base 13/50
1 Hibás válasz 0/0 3ms 1700 KiB
2 Hibás válasz 0/0 17ms 5808 KiB
3 Elfogadva 2/2 3ms 2080 KiB
4 Elfogadva 2/2 3ms 2284 KiB
5 Elfogadva 2/2 3ms 2372 KiB
6 Hibás válasz 0/2 3ms 2368 KiB
7 Hibás válasz 0/2 3ms 2636 KiB
8 Hibás válasz 0/2 3ms 2908 KiB
9 Elfogadva 2/2 3ms 2928 KiB
10 Hibás válasz 0/2 3ms 2952 KiB
11 Elfogadva 2/2 3ms 3240 KiB
12 Hibás válasz 0/2 3ms 3096 KiB
13 Hibás válasz 0/3 7ms 4084 KiB
14 Hibás válasz 0/3 10ms 5872 KiB
15 Elfogadva 3/3 13ms 6296 KiB
16 Hibás válasz 0/3 12ms 5896 KiB
17 Hibás válasz 0/3 8ms 5620 KiB
18 Hibás válasz 0/3 13ms 5872 KiB
19 Hibás válasz 0/3 14ms 6152 KiB
20 Hibás válasz 0/3 17ms 8184 KiB
21 Hibás válasz 0/3 19ms 8020 KiB
22 Hibás válasz 0/3 23ms 9232 KiB