Submission #385326

#	Time	Username	Problem	Language	Result	Execution time	Memory
385326		ParsaAlizadeh	Game (IOI14_game)	C++17	100 / 100	515 ms	18540 KiB

game

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

int const N = 1510;
int n, par[N], sz[N], cnt[N][N];

int find(int u) {
    return par[u] == -1 ? u : par[u] = find(par[u]);
}

int merge(int u, int v) {
    u = find(u), v = find(v);
    if (++cnt[u][v] == sz[u] * sz[v]) {
        par[v] = u;
        sz[u] += sz[v];
        for (int w = 0; w < n; w++)
            cnt[u][w] += cnt[v][w], cnt[w][u] += cnt[w][v];
        return true;
    }
    cnt[v][u]++;
    return false;
}

void initialize(int _n) {
    n = _n;
    fill(par, par + n, -1);
    fill(sz, sz + n, 1);
}

int hasEdge(int u, int v) {
    return merge(u, v);
}

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