Submission #216716

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

game

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

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

public:
    DSU(int n) {
        this->n = n;
        count = 0;
        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)]--;
        count++;
        return 0;
    }

    bool check() {
        return count < (n - 1) * (n - 2) / 2;
    }
};

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);
    if (pu == pv)
        return 1;
    if (dsu->get(pu) != 1 && dsu->get(pv) != 1 && dsu->check())
        return dsu->update(pu, pv);
    else
        return dsu->merge(pu, pv);
}

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