제출 #763021

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

game

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

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

mt19937 gen(69420);

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);
			}
		}
		shuffle(adj[i].begin(), adj[i].end(), gen);
	}
}

int hasEdge(int u, int v) {
	adj[u].erase(find(adj[u].begin(), adj[u].end(), v));
	adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
	int pt1 = 0;
	int sz1 = 1;
	int pt2 = 0;
	int sz2 = 1;
	q1[pt1] = u;
	flag[u] = t;
	q2[pt2] = v;
	flag[v] = t + 1;
	while (pt1 < sz1 && pt2 < sz2) {
		int x = q1[pt1++];
		for (auto y: adj[x]) {
			if (flag[y] == t + 1) {
				t += 2;
				return 0;
			}
			if (flag[y] != t) {
				flag[y] = t;
				q1[sz1++] = y;
			}
		}
		x = q2[pt2++];
		for (auto y: adj[x]) {
			if (flag[y] == t) {
				t += 2;
				return 0;
			}
			if (flag[y] != t + 1) {
				flag[y] = t + 1;
				q2[sz2++] = y;
			}
		}
	}
	t += 2;
	return 1;
}

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