Submission #1012006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012006		pcc	Game (IOI14_game)	C++17	100 / 100	243 ms	25232 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
 
const int mxn = 1505;
#define pii pair<int,int>
#define fs first
#define sc second
 
int n;
 
struct DSU{
	int dsu[mxn];
	int paths[mxn][mxn];
	void init(int n){
		for(int i = 0;i<n;i++)dsu[i] = i;
		for(int i = 0;i<n;i++){
			for(int j = 0;j<n;j++){
				if(i == j)continue;
				paths[i][j] = paths[j][i] = 1;
			}
		}
		return;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		paths[a][b] --;paths[b][a]--;
		a = root(a),b = root(b);
		if(a == b)return;
		dsu[b] = a;
		for(int i = 0;i<n;i++)paths[a][i] += paths[b][i];
		for(int i = 0;i<n;i++)paths[i][a] += paths[b][i];
		return;
	}
};
 
DSU dsu;
 
void initialize(int nn) {
	n = nn;
	dsu.init(n);
}
 
int hasEdge(int u, int v) {
	u = dsu.root(u),v = dsu.root(v);
	if(dsu.paths[u][v] != 1){
		dsu.paths[u][v]--;
		dsu.paths[v][u]--;
		return 0;
	}
	dsu.onion(u,v);
	return 1;
}

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