Submission #1147717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147717		KickingKun	Game (IOI14_game)	C++20	42 / 100	1091 ms	540 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

const int N = 1505;

int sz; bitset <N> adj[N];
void initialize(int n) {
	sz = n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (i != j) adj[i].set(j);
}

int hasEdge(int x, int y) {
    adj[x].reset(y); adj[y].reset(x); // try
    bitset <N> candidate; int n = sz;
    for (int i = 0; i < n; i++)
    	candidate.set(i);
    
    queue <int> q; q.emplace(0); candidate.reset(0);
    int cnt = 1;
    while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int v = 0; v < n; v++) {
			if (candidate.test(v) && adj[u].test(v)) {
				q.emplace(v); candidate.reset(v);
				++cnt;
			}
		}
	}
	
	if (cnt == n) return 0;
	else {
		adj[x].set(y); adj[y].set(x);
		return 1;
	}
}

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