Submission #875972

#	Time	Username	Problem	Language	Result	Execution time	Memory
875972		AlphaMale06	Game (IOI14_game)	C++14	100 / 100	265 ms	26708 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

const int N = 1501;
int cnt[N][N];

int p[N];
int sz[N];

void make(int i){
    p[i]=i;
    sz[i]=1;
}
int f(int a){
    if(p[a]==a)return a;
    return p[a]=f(p[a]);
}
void un(int u, int v){
    p[v]=u;
    sz[u]+=sz[v];
}

int hasEdge(int u, int v){
    u=f(u); v=f(v);
    int szu=sz[u];
    int szv=sz[v];
    int k=szu+szv;
    int num=k*(k-1)/2 - szu*(szu-1)/2 -szv*(szv-1)/2;
    if(cnt[u][v]==num-1){
        if(szu<szv){
            swap(u, v);
        }
        un(u, v);

        for(int i=0; i< N; i++){
            if(i!=u){
                cnt[u][i]+=cnt[v][i];
                cnt[i][u]+=cnt[v][i];
            }
        }
        return 1;
    }
    else{
        cnt[u][v]++;
        cnt[v][u]++;
        return 0;
    }
}

void initialize(int n){
    for(int i=0; i< n; i++)make(i);
}

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