Submission #599952

#	Time	Username	Problem	Language	Result	Execution time	Memory
599952		smth	Game (IOI14_game)	C++14	100 / 100	303 ms	10880 KiB

game

#include "game.h"
#include<iostream>
using namespace std;
long long N, par[1600], len[1600];
bool used[1501][1501];
void initialize(int n) {
    N=n;
    for(int i=0;i<n;i++){par[i]=i;len[i]=1;}
}
int find_par(int vr)
{
    if(vr==par[vr])return vr;
    return par[vr]=find_par(par[vr]);
}
void unite(int u,int v)
{
    u=find_par(u);
    v=find_par(v);

    if(len[u]<len[v])swap(u,v);

    par[v]=u;
    if(len[v]==len[u])len[v]++;
}

int hasEdge(int u, int v) {

    used[u][v]=used[v][u]=1;
    if((par[u]!=0 && par[v]!=0) || (par[u]==0 && par[v]==0))return 0;

    if(par[v]==0)swap(u,v);

        for(int i=0;i<N;i++)
        {
            if(i==u || i==v)continue;
            if(par[i]==0 && !used[i][v])return 0;
        }
    unite(u,v);
    return 1;

}

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