제출 #763003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
763003		SanguineChameleon	게임 (IOI14_game)	C++17	42 / 100	1068 ms	4236 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1.5e3 + 20;
vector<int> adj[maxn];
int q[maxn];
int flag[maxn];
int t;

void initialize(int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (j != i) {
				adj[i].push_back(j);
			}
		}
	}
}

mt19937 gen(69420);
uniform_int_distribution<int> dist(0, 1);

int hasEdge(int u, int v) {
	t++;
	adj[u].erase(find(adj[u].begin(), adj[u].end(), v));
	adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
	int pt = 0;
	int sz = 1;
	if (dist(gen)) {
		swap(u, v);
	}
	q[pt] = u;
	flag[u] = t;
	while (pt < sz) {
		int x = q[pt++];
		for (auto y: adj[x]) {
			if (y == v) {
				return 0;
			}
			if (flag[y] != t) {
				flag[y] = t;
				q[sz++] = y;
			}
		}
	}
	return 1;
}

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