Submission #745597

#	Time	Username	Problem	Language	Result	Execution time	Memory
745597		Username4132	Game (IOI14_game)	C++14	100 / 100	409 ms	25316 KiB

game

#include "game.h"
#include<iostream>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)

const int MAXN=1510;
int n, number[MAXN][MAXN], par[MAXN], si[MAXN];

int root(int a){
    while(par[a]!=a) a=par[a]=par[par[a]];
    return a;
}

void initialize(int N) {
    n=N;
    forn(i, n) par[i]=i, si[i]=1;
}

int hasEdge(int a, int b){
    int ra=root(a), rb=root(b);
    if(ra==rb) return 0;
    if(si[ra]<si[rb]) swap(ra, rb);
    if(si[ra]*si[rb]-1 == number[ra][rb]){
        forn(i, n) number[i][ra]+=number[i][rb];
        forn(i, n) number[ra][i]+=number[rb][i];
        si[ra]+=si[rb];
        par[rb]=ra;
        return 1;
    }
    else{
        number[ra][rb]++;
        number[rb][ra]++;
        return 0;
    }
}

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