Submission #719747

#	Time	Username	Problem	Language	Result	Execution time	Memory
719747		hoainiem	Game (IOI14_game)	C++14	100 / 100	454 ms	25420 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int N, par[1508], a[1508][1508];
vector<int>ds[1508];
int root(int x){
    return (par[x] < 0) ? x : (par[x] = root(par[x]));
}
void join(int u, int v){
    if ((u = root(u)) == (v = root(v)))
        return;
    if (par[u] > par[v])
        swap(u, v);
    par[u] += par[v];
    par[v] = u;
    for (int tmp : ds[v])
        ds[u].push_back(tmp);
    ds[v].clear();
}
void initialize(int n) {
    N = n;
    for (int i = 0; i < N; i++){
        par[i] = -1;
        ds[i].push_back(i);
    }
}

int hasEdge(int u, int v) {
    a[u][v]++;
    a[v][u]++;
    u = root(u);
    v = root(v);
    assert(u != v);
    for (int i : ds[u])
        for (int j : ds[v])
            if (!a[i][j])
                return 0;
    join(u, v);
    return 1;
}

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