Submission #519093

#	Time	Username	Problem	Language	Result	Execution time	Memory
519093		tabr	Game (IOI14_game)	C++17	100 / 100	380 ms	25216 KiB

game

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p = vector<int>(n);
        iota(p.begin(), p.end(), 0);
        sz = vector<int>(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }

    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }

    inline int size(int x) {
        return sz[get(x)];
    }

    inline bool root(int x) {
        return (x == get(x));
    }
};

int n;
int deg[1500][1500];
dsu uf(0);

void initialize(int _n) {
    n = _n;
    uf = dsu(n);
}

int hasEdge(int u, int v) {
    assert(!uf.same(u, v));
    int x = uf.get(u);
    int y = uf.get(v);
    deg[x][y]++;
    deg[y][x]++;
    if (deg[x][y] == uf.size(x) * uf.size(y)) {
        uf.unite(x, y);
        for (int i = 0; i < n; i++) {
            if (uf.root(i) && i != y) {
                deg[i][y] += deg[i][x];
                deg[y][i] += deg[x][i];
            }
        }
        return 1;
    } else {
        return 0;
    }
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}
#endif

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