Submission #748210

#	Time	Username	Problem	Language	Result	Execution time	Memory
748210		ZeroCool	Game (IOI14_game)	C++14	100 / 100	361 ms	25208 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define ll long long
#define inf INT_MAX

using namespace std;

const int mxn = 1505;

int pr[mxn];
int sz[mxn];
int ed[mxn][mxn];

int n;


int find(int x){
    if(pr[x ]== x)return x;
    return pr[x] = find(pr[x]);
}

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

int hasEdge(int a, int b) {
    a = find(a);
    b = find(b);

    if(sz[a] < sz[b])swap(a,b);
    if(sz[a] * sz[b]  > ed[a][b] + 1){
        ed[a][b] ++;
        ed[b][a] ++;
        return 0;
    }
    sz[a] += sz[b];
    pr[b] = a;
    for(int i = 0;i<n;i++){
        ed[a][i] += ed[b][i];
        ed[i][a] += ed[i][b];
    }
    return 1;
}

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