3281 2023. 02. 23 18:57:22 zsombor Egyirányú egyensúly cpp17 Elfogadva 50/50 46ms 8828 KiB
#include <iostream>
#include <vector>
using namespace std;

int n, m, a, b;
vector <int> e1;
vector <int> e2;
vector <int> fok(2e4 + 1, 0);
vector <int> ptn;
vector <vector <int>> g(2e4 + 1);
vector <bool> volt(6e4, false);
vector <bool> dir(6e4, false);

void del(int x) {
    swap(g[x][0], g[x].back());
    g[x].pop_back();
}

void euler(int x) {
    while (g[x].size()) {
        int i = g[x][0]; del(x);
        if (volt[i]) continue;
        volt[i] = true;
        dir[i] = (e1[i] == x);
        euler((e1[i] == x ? e2[i] : e1[i]));
    }
}

int main()
{
    cin >> n >> m;
    e1.resize(m); e2.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> e1[i] >> e2[i];
        fok[e1[i]]++;
        fok[e2[i]]++;
    }
    for (int i = 1; i <= n; i++) if (fok[i] % 2) ptn.push_back(i);
    for (int i = 0; i < ptn.size(); i += 2) {
        e1.push_back(ptn[i]);
        e2.push_back(ptn[i + 1]);
    }
    for (int i = 0; i < e1.size(); i++) {
        g[e1[i]].push_back(i);
        g[e2[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) euler(i);
    cout << ptn.size() << endl;
    for (int i = 0; i < m; i++) cout << (dir[i] ? "-> " : "<- ");
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 2708 KiB
2 Elfogadva 0/0 34ms 6580 KiB
3 Elfogadva 2/2 3ms 3192 KiB
4 Elfogadva 2/2 3ms 3404 KiB
5 Elfogadva 2/2 3ms 3392 KiB
6 Elfogadva 2/2 3ms 3396 KiB
7 Elfogadva 2/2 3ms 3600 KiB
8 Elfogadva 2/2 3ms 4160 KiB
9 Elfogadva 2/2 3ms 3904 KiB
10 Elfogadva 2/2 4ms 4380 KiB
11 Elfogadva 2/2 4ms 4508 KiB
12 Elfogadva 2/2 4ms 4556 KiB
13 Elfogadva 3/3 10ms 5188 KiB
14 Elfogadva 3/3 18ms 6232 KiB
15 Elfogadva 3/3 21ms 7932 KiB
16 Elfogadva 3/3 25ms 7536 KiB
17 Elfogadva 3/3 13ms 6552 KiB
18 Elfogadva 3/3 27ms 7228 KiB
19 Elfogadva 3/3 27ms 6920 KiB
20 Elfogadva 3/3 37ms 8344 KiB
21 Elfogadva 3/3 41ms 8160 KiB
22 Elfogadva 3/3 46ms 8828 KiB