Submission #369803

#	Time	Username	Problem	Language	Result	Execution time	Memory
369803		arnold518	Game (IOI14_game)	C++14	100 / 100	532 ms	25452 KiB

game

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1500;

int N;

int cnt[MAXN+10][MAXN+10];

struct UF
{
	int par[MAXN+10], sz[MAXN+10];
	int Find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=Find(par[x]);
	}
	void Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		if(x==y) return;
		for(int i=1; i<=N; i++)
		{
			cnt[y][i]+=cnt[x][i];
			cnt[i][y]+=cnt[i][x];
			cnt[x][i]=0;
			cnt[i][x]=0;
		}
		sz[y]+=sz[x];
		par[x]=y;
	}
}uf;

void initialize(int _N)
{
	N=_N;
	for(int i=1; i<=N; i++) uf.par[i]=i, uf.sz[i]=1;
}

int hasEdge(int u, int v)
{
	u++; v++;
	u=uf.Find(u); v=uf.Find(v);
	cnt[u][v]++; cnt[v][u]++;
	//printf("%d %d\n", cnt[u][v], uf.sz[u]*uf.sz[v]);
	if(cnt[u][v]==uf.sz[u]*uf.sz[v])
	{
		uf.Union(u, v);
		return 1;
	}
	return 0;
}

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