Submission #1025464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025464		onbert	Game (IOI14_game)	C++17	100 / 100	266 ms	26600 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1505;
int n;
int adj[maxn][maxn];
int fa[maxn], sz[maxn];
int rt(int u) {
    if (fa[u] == u) return u;
    else return fa[u] = rt(fa[u]);
}

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

int hasEdge(int u, int v) {
    int U = rt(u), V = rt(v);
    // cout << U << " " << V << endl;
    // cout << adj[U][V] << " " << adj[V][U] << " " << sz[U] << " " << sz[V] << endl;
    if (adj[U][V] == sz[U] * sz[V] - 1) {
        for (int i=0;i<n;i++) adj[V][i] += adj[U][i], adj[U][i] = 0;
        for (int i=0;i<n;i++) adj[i][V] += adj[i][U], adj[i][U] = 0;
        fa[U] = V;
        sz[V] += sz[U];
        return 1;
    }
    adj[U][V]++, adj[V][U]++;
    return 0;
}

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