Submission #735848

#	Time	Username	Problem	Language	Result	Execution time	Memory
735848		esomer	Game (IOI14_game)	C++17	100 / 100	388 ms	25232 KiB

game

#include<bits/stdc++.h>
 
using namespace std;
 
struct DSU{
	vector<int> v;
	vector<vector<int>> deg;
	void init(int n){v.assign(n, -1); deg.assign(n, vector<int>(n, 0));}
	int get(int x){return v[x] < 0 ? x : v[x] = get(v[x]);}
	int unite(int x, int y){
		x = get(x); y = get(y);
		if(x == y) return 0;
		deg[x][y]++; deg[y][x]++;
		if(deg[x][y] != v[x] * v[y]) return 0;
		if(v[x] > v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x;
		for(int i = 0; i < (int)v.size(); i++){
			if(v[i] < 0){
				deg[i][x] += deg[i][y];
				deg[x][i] += deg[y][i];
			}
		}
		return 1;
	}
};
 
DSU UF;
 
void initialize(int n){
	UF.init(n);
}
 
int hasEdge(int u, int v){
	return UF.unite(u, v);
}

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