Submission #1267527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267527		cmiuc	Game (IOI14_game)	C++20	42 / 100	1093 ms	5420 KiB

game

#include <iostream>
#include <vector>

#include "game.h"
using namespace std;
int Nn, cnt[1505], blocked[1505][1505], seen[1505], cur = 1, ver;
vector<int> nei[1505];

void initialize(int N){
	Nn = N;
	for (int i=1;i<=N;i++)
		for (int j=1;j<=N;j++)
			if (i != j)
				nei[i].push_back(j);
}

void dfs(int u){
	seen[u] = cur, ver++;
	for (int i : nei[u])
		if (!blocked[i][u] and seen[i] != cur)
			dfs(i);
}

int hasEdge(int u, int v){
	u++;
	v++;
	blocked[u][v] = blocked[v][u] = 1;
	cur++;
	ver = 0;
	dfs(1);

	if (ver == Nn)
		return 0;
	blocked[u][v] = blocked[v][u] = 0;
	return 1;
}

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