Submission #399587

#	Time	Username	Problem	Language	Result	Execution time	Memory
399587		Jasiekstrz	Game (IOI14_game)	C++17	100 / 100	473 ms	25288 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const int N=15e2;
int nn;
int cnt[N+10][N+10];
int fau[N+10];
int f(int x)
{
	if(fau[x]!=x)
		fau[x]=f(fau[x]);
	return fau[x];
}
void un(int x,int y)
{
	x=f(x);
	y=f(y);
	for(int i=0;i<nn;i++)
		cnt[x][i]=cnt[i][x]=cnt[x][i]+cnt[y][i];
	fau[y]=x;
	return;
}
void initialize(int n)
{
	nn=n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			cnt[i][j]=1;
		fau[i]=i;
	}
	return;
}
int hasEdge(int u,int v)
{
	u=f(u);v=f(v);
	//cerr<<u<<" "<<v<<"\n";
	if(cnt[u][v]>1)
	{
		cnt[u][v]--;
		cnt[v][u]--;
		return 0;
	}
	un(u,v);
    return 1;
}

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