Submission #738979

#	Time	Username	Problem	Language	Result	Execution time	Memory
738979		1ne	Game (IOI14_game)	C++14	0 / 100	1 ms	260 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<set<int>>pos;
vector<int>with;
int cur = 0;
void initialize(int n) {
	pos.resize(n);
	with.resize(n,0);
	cur = n - 2;
	for (int i = 0;i<n;++i){
		for (int j = 0;j<n;++j){
			if (i != j){
				pos[i].insert(j);
			}
		}
	}	
}
int hasEdge(int u, int v) {
	if (pos[u].find(v)==pos[u].end()){
		return 0;
	}
	 auto join = [&](int a,int b){
	 	vector<int>temp;
	 	for (auto x:pos[a]){
			if (pos[b].find(x) != pos[b].end()){
				temp.push_back(x);
			}
		}
		for (auto x:pos[b]){
			if (pos[a].find(x) != pos[a].end()){
				temp.push_back(x);
			}
		}
		for (auto x:temp){
			if (pos[a].find(x)!=pos[a].end()){
				pos[a].erase(x);
			}
			if (pos[b].find(x)!=pos[b].end()){
				pos[b].erase(x);
			}
		}
	 };
	 auto rem = [&](int a,int b){
	 	if (pos[a].find(b)!=pos[a].end()){
    		pos[a].erase(b);
    	}
    	if (pos[b].find(a)!=pos[b].end()){
    		pos[b].erase(a);
    	}
	 };
	 
	 if (((int)pos[u].size() == 1 && with[u] == 0 && with[v] == 0) || (with[u] == 0 && (int)pos[v].size() == 1 && with[v] == 0)){
	 	join(u,v);
	   rem(u,v);
	   with[u]++;
	   with[v]++;
		return 1;
	 }
	 else if (cur > 1 && ((int)pos[u].size() == 1 || pos[v].size() == 1) && with[u] == 1 && with[v] == 1){
	 	join(u,v);
	   rem(u,v);
	   with[u]++;
	   with[v]++;
	   cur-=2;
		return 1;
	 }
	 else if (cur > 0 && ((int)pos[u].size() == 1  || (int)pos[v].size() == 1) && (with[u] + with[v]) == 1){
	 	join(u,v);
	   rem(u,v);
	   with[u]++;
	   with[v]++;
	   cur-=1;
		return 1;
	 }
    rem(u,v);
	 return 0;
}

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