Submission #634380

#	Time	Username	Problem	Language	Result	Execution time	Memory
634380		ljuba	Game (IOI14_game)	C++17	100 / 100	334 ms	28092 KiB

game

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

using namespace std;

int n;

const int mxN = 2004;

int dsu[mxN];
int vel[mxN];

int cnt[mxN][mxN];

int findSet(int u) {
    if(dsu[u] == u) return u;
    return dsu[u] = findSet(dsu[u]);
}

void initialize(int N) {
    n = N;
    iota(dsu, dsu + n, 0);
    fill(vel, vel + n, 1);
}

int hasEdge(int u, int v) {
    u = findSet(u);
    v = findSet(v);

    if(u == v) return 0;

    ++cnt[u][v], ++cnt[v][u];

    if(cnt[u][v] == vel[u] * vel[v]) {
        //join
        if(vel[u] > vel[v]) swap(u, v); //vel[u] <= vel[v]

        vel[v] += vel[u];
        dsu[u] = v;

        for(int i = 0; i < n; ++i) {
            if(i == v) continue;
            cnt[v][i] += cnt[u][i];
            cnt[i][v] += cnt[i][u];
        }

        return 1;
    } else {
        return 0;
    }
}

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