Submission #763008

#	Time	Username	Problem	Language	Result	Execution time	Memory
763008		SanguineChameleon	Game (IOI14_game)	C++17	42 / 100	1087 ms	3240 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 flag1[maxn];
int q2[maxn];
int flag2[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);
			}
		}
	}
}

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 pt1 = 0;
	int sz1 = 1;
	int pt2 = 0;
	int sz2 = 1;
	q1[pt1] = u;
	flag1[u] = t;
	q2[pt2] = v;
	flag2[u] = t;
	while (pt1 < sz1 && pt2 < sz2) {
		int x = q1[pt1++];
		for (auto y: adj[x]) {
			if (y == v) {
				return 0;
			}
			if (flag1[y] != t) {
				flag1[y] = t;
				q1[sz1++] = y;
			}
		}
		x = q2[pt2++];
		for (auto y: adj[x]) {
			if (y == u) {
				return 0;
			}
			if (flag2[y] != t) {
				flag2[y] = t;
				q2[sz2++] = y;
			}
		}
	}
	return 1;
}

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