Submission #693781

#	Time	Username	Problem	Language	Result	Execution time	Memory
693781		T0p_	Game (IOI14_game)	C++14	0 / 100	1 ms	212 KiB

game

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

int n;
int pa[1500], sz[1500];
bool assigned[1500][1500];

int fp(int u) { return pa[u] = (u == pa[u]) ? u : fp(pa[u]); }

void initialize(int N)
{
    n = N;
	for (int i=0 ; i<n ; i++)
    {
        pa[i] = i;
        sz[i] = 1;
    }
}
 
int hasEdge(int u, int v)
{
    assigned[u][v] = assigned[v][u] = true;

    int uu = fp(u), vv = fp(v);

    if (uu == vv) return 0;

    int cnt = 0;

    for (int i=0 ; i<n ; i++) if (fp(i) == uu)
    {
        for (int j=i+1 ; j<n ; j++) if (fp(j) == vv)
        {
            if (assigned[i][j]) cnt += 1;
        }
    }

    if (cnt != sz[uu] * sz[vv]) return 0;

    pa[uu] = vv;
    sz[vv] += sz[uu];
    return 1;
}

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