Submission #856455

#	Time	Username	Problem	Language	Result	Execution time	Memory
856455		nnin	Game (IOI14_game)	C++14	100 / 100	251 ms	26708 KiB

game

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,int>
using namespace std;

int n, dsu[1505], sz[1505], ct[1505][1505];

int par(int x) {
    if(dsu[x]==-1) return x;
    return dsu[x] = par(dsu[x]);
}

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

int hasEdge(int u, int v) {
    u = par(u);
    v = par(v);
    if(ct[u][v]+1<sz[u]*sz[v]) {
        ct[u][v]++;
        ct[v][u]++;
        return 0;
    }
    dsu[v] = u;
    sz[u] += sz[v];
    for(int i=0;i<n;i++) {
        if(par(i)!=i || i==u) continue;
        ct[u][i] = ct[i][u] = ct[u][i]+ct[v][i];
    }
    return 1;
} 

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