Submission #416142

#	Time	Username	Problem	Language	Result	Execution time	Memory
416142		dxz05	Game (IOI14_game)	C++14	0 / 100	0 ms	204 KiB

game

#include "game.h"

const int MAXN = 111111;

int p[MAXN], sz[MAXN], deg[MAXN], ask_count[MAXN];
int find(int x){
    return (x == p[x] ? x : p[x] = find(p[x]));
}

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if (x == y) return;
    p[x] = y;
    sz[y] += sz[x];
}

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

int hasEdge(int u, int v) {
    ask_count[u]++;
    ask_count[v]++;
    if (find(u) == find(v)) return 0;
    if (sz[p[u]] + sz[p[v]] == n) return 0;
    if (ask_count[u] == n - 1 && deg[u] == n - 2) return 0;
    if (ask_count[v] == n - 1 && deg[v] == n - 2) return 0;

    unite(u, v);
    deg[u]++;
    deg[v]++;
    
    return 0;
}

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