32802023-02-23 18:27:00zsomborEgyirányú egyensúlycpp17Wrong answer 4/5043ms7868 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] ? "-> " : "<- ");
}
SubtaskSumTestVerdictTimeMemory
base4/50
1Wrong answer0/03ms2456 KiB
2Wrong answer0/032ms5008 KiB
3Accepted2/23ms2992 KiB
4Wrong answer0/23ms3200 KiB
5Accepted2/23ms3416 KiB
6Wrong answer0/23ms3520 KiB
7Wrong answer0/23ms3808 KiB
8Wrong answer0/23ms3652 KiB
9Wrong answer0/23ms3652 KiB
10Wrong answer0/24ms3660 KiB
11Wrong answer0/24ms4256 KiB
12Wrong answer0/24ms4428 KiB
13Wrong answer0/39ms4940 KiB
14Wrong answer0/318ms6600 KiB
15Wrong answer0/321ms7280 KiB
16Wrong answer0/323ms6352 KiB
17Wrong answer0/312ms5784 KiB
18Wrong answer0/324ms6320 KiB
19Wrong answer0/325ms6460 KiB
20Wrong answer0/335ms7604 KiB
21Wrong answer0/337ms7156 KiB
22Wrong answer0/343ms7868 KiB