Submission #577037

#	Time	Username	Problem	Language	Result	Execution time	Memory
577037		Noam527	Game (APIO22_game)	C++17	0 / 100	0 ms	208 KiB

game

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

int getbits(int cnt) {
	return (1 << cnt) - 1;
}

int n, k;
vector<vector<int>> g, grev;
vector<int> s, e;

void initial_colors(int layer, int l, int r) {
	if (l == r) return;
	int mid = (l + r) / 2;
	for (int i = mid + 1; i <= r; i++)
		s[i] |= 1 << layer, e[i] |= 1 << layer;
	initial_colors(layer + 1, l, mid);
	initial_colors(layer + 1, mid + 1, r);
}

void init(int nn, int kk) {
	n = nn;
	k = kk;
	g.resize(n);
	grev.resize(n);
	s.resize(n);
	e.resize(n);

	initial_colors(0, 0, k - 1);
}

void forward_dfs(int layer, int need, int v) {
	if ((e[v] & getbits(layer)) != need) return;
	if (s[v] & (1 << layer)) return;
	s[v] |= 1 << layer;
	for (const auto &w : g[v])
		forward_dfs(layer, need, w);
}

void backward_dfs(int layer, int need, int v) {
	if ((s[v] & getbits(layer)) != need) return;
	if (~e[v] & (1 << layer)) return;
	e[v] ^= 1 << layer;
	for (const auto &w : grev[v])
		backward_dfs(layer, need, w);
}

int add(int layer, int l, int r, int u, int v) {
	if (l == r) return 0;
	if ((s[u] & (1 << layer)) && (~e[v] & (1 << layer))) return 1; // win
	if ((~s[u] & (1 << layer)) && (e[v] & (1 << layer))) return 0; // nothing more to discover...

	if (s[u] & (1 << layer))
		forward_dfs(layer, s[u] & getbits(layer), v);
	if (~e[v] & (1 << layer))
		backward_dfs(layer, e[v] & getbits(layer), u);

	int mid = (l + r) / 2;
	if (s[u] & (1 << layer))
		return add(layer + 1, mid + 1, r, u, v);
	return add(layer + 1, l, mid, u, v);
}

int add_teleporter(int u, int v) {
	g[u].push_back(v);
	grev[v].push_back(u);
	return add(0, 0, k - 1, u, v);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40