Submission #369113

#	Time	Username	Problem	Language	Result	Execution time	Memory
369113		mjhmjh1104	Game (IOI14_game)	C++14	0 / 100	1 ms	364 KiB

game

#include "game.h"

int uf[1506], sz[1506], ds[1506], n;

int _find(int x) {
    if (uf[x] == -1) return x;
    return uf[x] = _find(uf[x]);
}

void _merge(int x, int y) {
    x = _find(x), y = _find(y);
    if (x == y) return;
    sz[y] += sz[x], uf[x] = y;
}

void initialize(int N) {
    n = N;
    for (int i = 0; i < n; i++) uf[i] = -1, sz[i] = 1;
}

int hasEdge(int u, int v) {
    u = _find(u), v = _find(v);
    if (ds[u] + 1 == sz[u] * (n - sz[u]) || ds[v] + 1 == sz[v] * (n - sz[v])) {
        _merge(u, v);
        return 1;
    }
    ds[u]++, ds[v]++;
    return 0;
}

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