Submission #798190

#	Time	Username	Problem	Language	Result	Execution time	Memory
798190		QwertyPi	Game (IOI14_game)	C++14	100 / 100	365 ms	18068 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

struct DSU{
	int n, dsu[1511], a[1511][1511];
	void init(int n){
		DSU::n = 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) a[i][j] = 1;
			}
		}
	}
	int f(int x){
		return x == dsu[x] ? x : dsu[x] = f(dsu[x]);
	}
	bool g(int x, int y){
		x = f(x), y = f(y);
		if(x == y) return false;
		if(a[x][y] > 1) {
			a[x][y]--; a[y][x]--; return false;
		}else{
			dsu[x] = y;
			for(int i = 0; i < n; i++){
				if(f(i) == i && f(i) != y){
					a[i][y] += a[i][x];
					a[y][i] += a[x][i];
				}
			}
		}
		return true;
	}
} dsu;
void initialize(int n) {
	dsu.init(n);
}

int hasEdge(int u, int v) {
    return dsu.g(u, v);
}

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