Submission #417017

#	Time	Username	Problem	Language	Result	Execution time	Memory
417017		vanic	Game (IOI14_game)	C++14	42 / 100	1095 ms	2380 KiB

game

#include "game.h"
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <ctime>
#include <cstdlib>
#include <bitset>

using namespace std;

const int maxn=1505;

vector < int > ms[maxn];

int parent[maxn];
int n;

void precompute(){
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i!=j){
				ms[i].push_back(j);
			}
		} 
		parent[i]=i;
	}
}
int find(int x){
	if(parent[x]==x){
		return x;
	}
	return parent[x]=find(parent[x]);
}
void update(int x, int y){
	x=find(x);
	y=find(y);
	if(ms[x].size()>ms[y].size()){
		swap(x, y);
	}
	while(!ms[x].empty()){
		ms[y].push_back(ms[x].back());
		ms[x].pop_back();
	}
	parent[x]=y;
}
bool query(int x, int y){
	return find(x)==find(y);
}

void initialize(int a){
	n=a;
	srand(time(NULL));
	precompute();
}

bitset < maxn > bio;

void dfs(int x){
	x=find(x);
	if(bio[x]){
		return;
	}
	bio[x]=1;
	for(int i=0; i<(int)ms[x].size(); i++){
		dfs(ms[x][i]);
	}
}

int hasEdge(int x, int y){
	int nx=find(x);
	int ny=find(y);
	ms[nx].erase(find(ms[nx].begin(), ms[nx].end(), y));
	ms[ny].erase(find(ms[ny].begin(), ms[ny].end(), x));
	dfs(nx);
	bool p;
	if(bio[ny]){
		p=0;
	}
	else{
		p=1;
		update(x, y);
	}
	bio.reset();
	return p;
}

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