Submission #109216

#	Time	Username	Problem	Language	Result	Execution time	Memory
109216		nvmdava	Game (IOI14_game)	C++17	100 / 100	848 ms	25380 KiB

game

#include "game.h"
#define N 1501

int p[N], sz[N];
int cnt[N][N];

int find(int x){
    return (x == p[x] ? x : p[x] = find(p[x]));
}

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

int hasEdge(int u, int v) {
    v = find(v);
    u = find(u);
    cnt[v][u]++;
    cnt[u][v]++;
    if(cnt[v][u] != sz[v] * sz[u]) return 0;
    if(v > u){
        int a = v;
        v = u;
        u = a;
    }
    p[u] = v;
    sz[v] += sz[u];
    for(int i = 0; i < N; i++)cnt[v][i] += cnt[u][i], cnt[i][v] = cnt[v][i];
    return 1;
}

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