Submission #1039217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039217		VMaksimoski008	Game (IOI14_game)	C++17	100 / 100	222 ms	25172 KiB

game

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

int cnt[1505][1505], par[1505], sz[1505], N;

int find(int u) {
    if(u == par[u]) return u;
    return par[u] = find(par[u]);
}

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

int hasEdge(int u, int v) {
    u = find(u); v = find(v);
    if(u == v) return 1;

    if(sz[u] * sz[v] == cnt[u][v] + 1) {
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
        for(int i=0; i<N; i++) {
            cnt[u][i] += cnt[v][i];
            cnt[i][u] += cnt[v][i];
        }
        return 1;
    }

    cnt[u][v]++; cnt[v][u]++;
    return 0;
}

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