Submission #558477

#	Time	Username	Problem	Language	Result	Execution time	Memory
558477		heavylightdecomp	Game (IOI14_game)	C++14	100 / 100	388 ms	24316 KiB

game

#include<bits/stdc++.h>
using namespace std;
int par[1505], dp[1505][1505];
set<int> rep;
int find(int x) { if(x==par[x])return x;else return par[x]=find(par[x]); }
void merge(int a, int b) { 
	a = find(a), b = find(b); if(a==b)return;
	rep.erase(a);
	for(auto it : rep) dp[b][it] = dp[it][b] = dp[b][it] + dp[a][it];
	par[a]=b;
}
void initialize(int n){ 
	for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) dp[i][j] = 1; 
	for(int i = 0; i < n; i++) rep.insert(i), par[i]=i;
}
int hasEdge(int u, int v) {
	if(find(u)==find(v)) 
		return 0; 
	if(dp[find(u)][find(v)] == 1) {merge(u,v); return 1;}
	dp[find(u)][find(v)]--, dp[find(v)][find(u)]--;
	return 0;
}

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