Submission #259797

#	Time	Username	Problem	Language	Result	Execution time	Memory
259797		errorgorn	Game (IOI14_game)	C++14	100 / 100	514 ms	25336 KiB

game

#include "game.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int n;
int par[1505];
int ss[1505];
int cnt[1505][1505];
bool alive[1505];

int parent(int i){
	if (par[i]==i) return i;
	else return par[i]=parent(par[i]);	
}

void initialize(int N) {
	n=N;
	rep(x,0,1505){
		par[x]=x;
		ss[x]=1;
		alive[x]=true;
	}
}

int hasEdge(int u, int v) {
	u=parent(u),v=parent(v);	
	
	cnt[u][v]++;
	cnt[v][u]++;
	
	if (cnt[u][v]==ss[u]*ss[v]){
		par[v]=u;
		ss[u]+=ss[v];
		alive[v]=false;
		rep(x,0,n) if (alive[x]){
			cnt[u][x]+=cnt[v][x];
			cnt[x][u]+=cnt[x][v];
		}
		
		return 1;
	}
	else{
		return 0;	
	}
}

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