Submission #1059023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059023		oscarsierra12	Game (IOI14_game)	C++14	100 / 100	205 ms	26596 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1510;

int fat[N], sz[N];
int nedges[N][N];
int nn = 0;

void ini(int n) {
    for (int i = 0; i < n; ++i) fat[i] = i, sz[i] = 1;
}

int fnd (int x) {
    if (x == fat[x]) return x;
    return fat[x] = fnd(fat[x]);
}

void uni (int x, int y) { 
    int fx = fnd(x), fy = fnd(y);
    fat[fx] = fy;
    sz[fy] += sz[fx];

    for (int z = 0; z < nn; ++z) { 
        nedges[fy][z] += nedges[fx][z];
        nedges[z][fy] += nedges[z][fx];
    }
}

void initialize(int n) {
    nn = n;
    ini(n);
}

int hasEdge(int u, int v) {
    if (nedges[fnd(u)][fnd(v)] == sz[fnd(u)] * sz[fnd(v)] - 1) { 
        uni(u, v);
        return 1;
    }
    nedges[fnd(u)][fnd(v)]++;
    nedges[fnd(v)][fnd(u)]++;
    return 0;
}

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