Submission #1012005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012005		pcc	Game (IOI14_game)	C++17	42 / 100	183 ms	4948 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

const int mxn = 1505;
#define int short
#define pii pair<int,int>
#define fs first
#define sc second

int n;

struct DSU{
	short dsu[mxn];
	short 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(int32_t nn) {
	n = nn;
	dsu.init(n);
}

int32_t hasEdge(int32_t u, int32_t v) {
	u = dsu.root(u),v = dsu.root(v);
	if(dsu.paths[u][v] != 1){
		cerr<<"NO MERGE\n";
		dsu.paths[u][v]--;
		dsu.paths[v][u]--;
		return 0;
	}
	cerr<<"MERGE\n";
	dsu.onion(u,v);
	return 1;
}

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