Submission #413462

#	Time	Username	Problem	Language	Result	Execution time	Memory
413462		Antekb	Game (IOI14_game)	C++14	100 / 100	508 ms	25288 KiB

game

#include "game.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=1505;
int E[N][N];
int n;
int r[N];
void initialize(int _n){
	n=_n;
	//cout<<n<<"\n";
	for(int i=0; i<n; i++){
		r[i]=i;
		for(int j=0; j<i; j++){
			E[i][j]=E[j][i]=1;
		}
	}
}
int find(int v){
	if(r[v]==v)return v;
	return r[v]=find(r[v]);
}
void Union(int u, int v){
//cout<<u<<"a"<<v<<"\n";
	
	for(int i=0; i<n; i++){
		if(i==u || i==v)continue;
		E[u][i]+=E[v][i];
		E[i][u]+=E[i][v];
		E[v][i]=0;
		E[i][v]=0;
		assert(E[u][i]==E[i][u]);
	}
	r[v]=u;
}
int hasEdge(int u, int v) {
	//cout<<u<<" "<<v<<"\n";
	u=find(u);
	v=find(v);
	assert(u!=v);
	E[u][v]--;
	E[v][u]--;
	/*for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cout<<E[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<<"\n";*/
	if(E[v][u]==0){
		Union(u, v);
		return 1;
	}
    return 0;
}

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