Submission #1147529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147529		KickingKun	Game (IOI14_game)	C++20	0 / 100	1 ms	328 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 u, int v) {
    adj[u].reset(v); adj[v].reset(u); // 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();
		int v = (candidate & adj[u])._Find_first();
		if (v < N) q.emplace(v), candidate.reset(v), ++cnt;
	}
	
	if (cnt == n) return 0;
	else {
		adj[u].set(v); adj[v].set(u);
		return 1;
	}
}

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