Submission #921213

#	Time	Username	Problem	Language	Result	Execution time	Memory
921213		pera	Game (IOI14_game)	C++17	100 / 100	297 ms	27360 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N = 1500 + 1;
int X;
vector<int> parent(N);
vector<vector<int>> bad(N + 1 , vector<int>(N + 1));
void initialize(int n){
	++n;
	X = n;
	for(int i = 1;i <= n;i ++){
		parent[i] = i;
		for(int j = 1;j <= n;j ++){
			bad[i][j] = (i != j);
		}
	}
}
int find(int u){
	return (u == parent[u] ? u : parent[u] = find(parent[u])); 
}
void unite(int u , int v){
	u = find(u);
	v = find(v);
	if(u != v){
		bad[u][v] = bad[v][u] = 0;
		for(int x = 1;x <= X;x ++){
			if(x != u && x != v){
				bad[x][u] += bad[x][v];
				bad[u][x] = bad[x][u];
			}
		}
		parent[v] = u;
	}
}
int hasEdge(int u , int v){
	++u , ++v;
	int U = find(u) , V = find(v);
	if(U == V){
		return 0;
	}
	if(bad[U][V] == 1){
		unite(u , v);
		return 1;
	}else{
		bad[U][V]--;
		bad[V][U]--;
		return 0;
	}
}/*
int main(){
	int n;
	cin >> n;
	initialize(n);
	for(int i = 1;i <= n * (n + 1) / 2;i ++){
		int u , v;
		cin >> u >> v;
		cout << hasEdge(u , v) << endl;
	}
}*/

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