Submission #216713

#	Time	Username	Problem	Language	Result	Execution time	Memory
216713		DS007	Game (IOI14_game)	C++14	0 / 100	5 ms	384 KiB

game

#include <bits/stdc++.h>
using namespace std;

class DSU {
    int *par, *val;
    int n;

public:
    DSU(int n) {
        this->n = n;
        par = new int[n];
        val = new int[n];
        iota(par, par + n, 0);
        fill(val, val + n, n - 1);
    }

    int find(int v) {
        if (v == par[v])
            return v;
        else
            return par[v] = find(par[v]);
    }

    int merge(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb)
            return 0;

        par[pa] = pb;
        val[pb] += val[pa] - 2;
        return 1;
    }

    int get(int v) {
        return val[find(v)];
    }

    int update(int u, int v) {
        val[find(u)]--;
        val[find(v)]--;
        return 0;
    }
};

DSU *dsu;

void initialize(int n) {
    dsu = new DSU(n);
}

int hasEdge(int u, int v) {
    int pu = dsu->find(u), pv = dsu->find(v);
    assert(pu != pv);
    if (dsu->get(pu) != 1 && dsu->get(pv) != 1)
        return dsu->update(pu, pv);
    else
        return dsu->merge(pu, pv);
}

/*signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;
    initialize(n);

    for (int i = 0; i < n * (n - 1) / 2; i++) {
        int u, v;
        cin >> u >> v;
        cout << hasEdge(u, v) << endl;
    }
}*/

• Subtask 1: 0 / 15
• Subtask 2: 0 / 27
• Subtask 3: 0 / 58