Submission #1038936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038936		mateuszwes	Game (IOI14_game)	C++17	100 / 100	203 ms	20308 KiB

game

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define F first
#define S second
#define pb push_back
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pq priority_queue

#include "game.h"
 
using namespace std;
constexpr int debug = 1;
constexpr int N = 1507;

//queue<int> possible_tree[N];
int possible_connect[N];
bool no_edge[N][N];
bool istree[N];
int vertices;
bool first = 1;

void initialize(int n){
	vertices = n;
}

void add_tree(int s){
	istree[s] = 1;
	for(int i = 0; i < vertices; i++){
		if((!istree[i]) && (!no_edge[i][s])){
			//possible_tree[i].push(s);
			possible_connect[i]++;
		}
	}
}

int hasEdge(int u, int v){
	if(istree[u] && istree[v]) return 1;
	else if(first){
		first = 0;
		add_tree(u);
		add_tree(v);
		return 1;
	}
	else if(istree[u] || istree[v]){
		if(istree[u]) swap(v,u);
		if(possible_connect[u] == 1){
			add_tree(u);
			return 1;
		}
		else{
			possible_connect[u]--;
		}

	}
	no_edge[u][v] = no_edge[v][u] = 1;
    return 0;
}

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