Submission #746176

#	Time	Username	Problem	Language	Result	Execution time	Memory
746176		mnbvcxz123	Game (IOI14_game)	C++17	100 / 100	425 ms	25216 KiB

game

#include<bits/stdc++.h>
int n;
int g[1505][1505];

struct DSU{
	int p[1505];
	void init(){memset(p,-1,sizeof(p));}
	int find(int x){
		if(p[x]<0)return x;
		return p[x]=find(p[x]);
	}
	void unite(int a, int b){
		a=find(a);
		b=find(b);
		if(a==b)return;
		p[a]+=p[b];
		p[b]=a;
	}
	int get(int x){return -p[find(x)];}
}dsu;

void initialize(int N){
	n=N;
	dsu.init();
}

int hasEdge(int a, int b){
	a=dsu.find(a);
	b=dsu.find(b);
	++g[a][b],++g[b][a];
	if(g[a][b]==dsu.get(a)*dsu.get(b)){
		dsu.unite(a,b);
		for(int i=0;i<n;++i){
			g[a][i]+=g[b][i];
			g[i][a]+=g[i][b];
		}
		return 1;
	}
	return 0;
}	

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