Submission #136190

#	Time	Username	Problem	Language	Result	Execution time	Memory
136190		zoooma13	Game (IOI14_game)	C++14	100 / 100	546 ms	16120 KiB

game

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

#define MAX_N 1503

int n;
int par[MAX_N] ,sz[MAX_N] ,con[MAX_N][MAX_N];
void initialize(int N){ n = N;
    iota(par ,par+n ,0);
    fill(sz ,sz+n ,1);
    memset(con ,0 ,sizeof con);
}

int fnd(int u){
    return par[u] = (par[u] == u ? u : fnd(par[u]));
}
void unn(int u ,int v){
    u = fnd(u) ,v = fnd(v);
    par[u] = v ,sz[v] += sz[u];
    for(int w=0; w<n; w++){
        con[v][w] += con[u][w];
        con[w][v] += con[w][u];
    }
}

int hasEdge(int u, int v){
    u = fnd(u) ,v = fnd(v);
    assert(u != v);
    con[u][v]++;
    con[v][u]++;
    if(con[u][v] == sz[u]*sz[v]){
        unn(u ,v);
        return 1;
    }
    return 0;
}

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