Submission #1026973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026973		socpite	Game (IOI14_game)	C++17	100 / 100	224 ms	31576 KiB

game

#include "game.h"

const int maxn = 2e3+5;

int up[maxn];
int cnt[maxn][maxn];

int N;

int Find(int x){
    return up[x] < 0 ? x : up[x] = Find(up[x]);
}

void Union(int a, int b){
    for(int i = 0; i < N; i++){
        if(up[i] >= 0)continue;
        cnt[a][i] += cnt[b][i];
        cnt[i][a] += cnt[b][i];
    }
    up[a] += up[b];
    up[b] = a;
}

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

int hasEdge(int u, int v) {
    int ra = Find(u), rb = Find(v);
    cnt[ra][rb]++;
    cnt[rb][ra]++;
    if(cnt[ra][rb] == up[ra]*up[rb]){
        Union(ra, rb);
        return 1;
    }
    return 0;
}

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