Submission #596992

#	Time	Username	Problem	Language	Result	Execution time	Memory
596992		Bench0310	Game (IOI14_game)	C++17	100 / 100	365 ms	22412 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;
typedef long long ll;

const int N=1500;
int n;
int p[N];
int sz[N];
int c[N][N];

void initialize(int _n)
{
    n=_n;
    for(int i=0;i<n;i++)
    {
        p[i]=i;
        sz[i]=1;
    }
}

int find_set(int a)
{
    if(a==p[a]) return a;
    else return p[a]=find_set(p[a]);
}

int merge_sets(int a,int b)
{
    a=find_set(a);
    b=find_set(b);
    c[a][b]++; c[b][a]++;
    if(c[a][b]==sz[a]*sz[b])
    {
        if(sz[a]<sz[b]) swap(a,b);
        p[b]=a;
        sz[a]+=sz[b];
        for(int i=0;i<n;i++)
        {
            if(i==a||i==b) continue;
            c[a][i]+=c[b][i];
            c[i][a]+=c[i][b];
        }
        return 1;
    }
    return 0;
}

int hasEdge(int u, int v)
{
    return merge_sets(u,v);
}

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