Submission #693800

#	Time	Username	Problem	Language	Result	Execution time	Memory
693800		T0p_	Game (IOI14_game)	C++14	42 / 100	1093 ms	3032 KiB

game

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

int n;
int pa[1500], sz[1500];
bool Asked[1500][1500];
vector<int> g[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)
{
    Asked[u][v] = Asked[v][u] = true;

    int uu = fp(u), vv = fp(v);
    if (uu == vv) return 0;

    int cntAsked = 0;
    stack<int> s1;
    s1.push(uu);

    while (!s1.empty())
    {
        int u = s1.top();
        s1.pop();

        stack<int> s2;
        s2.push(vv);

        while (!s2.empty())
        {
            int v = s2.top();
            s2.pop();

            if (Asked[u][v]) cntAsked += 1;

            for (int x : g[v]) s2.push(x);
        }

        for (int x : g[u]) s1.push(x);
    }

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

    pa[vv] = uu;
    sz[uu] += sz[vv];
    g[uu].push_back(vv);
    return 1;
}

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