3280 2023. 02. 23 18:27:00 zsombor Egyirányú egyensúly cpp17 Hibás válasz 4/50 43ms 7868 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(e2[i]);
        g[e2[i]].push_back(e1[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 4/50
1 Hibás válasz 0/0 3ms 2456 KiB
2 Hibás válasz 0/0 32ms 5008 KiB
3 Elfogadva 2/2 3ms 2992 KiB
4 Hibás válasz 0/2 3ms 3200 KiB
5 Elfogadva 2/2 3ms 3416 KiB
6 Hibás válasz 0/2 3ms 3520 KiB
7 Hibás válasz 0/2 3ms 3808 KiB
8 Hibás válasz 0/2 3ms 3652 KiB
9 Hibás válasz 0/2 3ms 3652 KiB
10 Hibás válasz 0/2 4ms 3660 KiB
11 Hibás válasz 0/2 4ms 4256 KiB
12 Hibás válasz 0/2 4ms 4428 KiB
13 Hibás válasz 0/3 9ms 4940 KiB
14 Hibás válasz 0/3 18ms 6600 KiB
15 Hibás válasz 0/3 21ms 7280 KiB
16 Hibás válasz 0/3 23ms 6352 KiB
17 Hibás válasz 0/3 12ms 5784 KiB
18 Hibás válasz 0/3 24ms 6320 KiB
19 Hibás válasz 0/3 25ms 6460 KiB
20 Hibás válasz 0/3 35ms 7604 KiB
21 Hibás válasz 0/3 37ms 7156 KiB
22 Hibás válasz 0/3 43ms 7868 KiB