Submission #577243

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

game

#include <bits/stdc++.h>
#include "game.h"
const int OO = 0;
using namespace std;

int getbits(int cnt) {
	return (1 << cnt) - 1;
}
void printbits(int v, int layers = 10) {
	for (int i = 0; i < layers; i++)
		cout << (v >> i & 1);
	cout << endl;
}

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;
	s[mid] |= 1 << layer;
	initial_colors(layer + 1, l, mid - 1);
	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);
	int layers = 1;
	while (getbits(layers) < k) layers++;
	for (int i = k; i < n; i++)
		e[i] = getbits(layers);
	if (OO) {
		cout << "initial colors:\n";
		for (int i = 0; i < n; i++) {
			cout << i << '\n';
			printbits(s[i]);
			printbits(e[i]);
		}
	}
}

void forward_dfs(int layer, int smask, int emask, int v) {
	if ((s[v] & smask) != smask || (e[v] & emask) != 0) return;
	if (s[v] & (1 << layer)) return;
	if (OO) {
		cout << "forward: " << v << '\n';
		printbits(s[v]);
		printbits(smask);
		printbits(emask);
	}
	s[v] |= 1 << layer;
	for (const auto &w : g[v])
		forward_dfs(layer, smask, emask, w);
}

void backward_dfs(int layer, int smask, int emask, int v) {
	if ((s[v] & smask) != smask || (e[v] & emask) != 0) return;
	if (~e[v] & (1 << layer)) return;
	if (OO) {
		cout << "backward: " << v << '\n';
		printbits(e[v]);
		printbits(smask);
		printbits(emask);
	}
	e[v] ^= 1 << layer;
	for (const auto &w : grev[v])
		backward_dfs(layer, smask, emask, w);
}

int add(int layer, int smask, int emask, int l, int r, int u, int v) {
	if (OO) {
		cout << "starting layer " << layer << " " << l << " " << r << '\n';
		printbits(s[u]);
		printbits(e[v]);
	}
	if (l > r) return 0;
	if ((s[u] & (1 << layer)) && (~e[v] & (1 << layer))) return 1;

	if (s[u] & (1 << layer)) {
		// forward dfs
		forward_dfs(layer, smask, emask, v);
	}
	if (~e[v] & (1 << layer)) {
		// backward dfs
		backward_dfs(layer, smask, emask, u);
	}

	int mid = (l + r) / 2;
	if (s[u] & (1 << layer)) {
		// return with added smask
		return add(layer + 1, smask | (1 << layer), emask, mid + 1, r, u, v);
	}
	else if (~e[v] & (1 << layer)) {
		// return with added emask
		return add(layer + 1, smask, emask | (1 << layer), l, mid - 1, u, v);
	}
	return 0;
}

void brute_dfs(vector<int> &vis, int v) {
	if (vis[v]) return;
	vis[v] = 1;
	for (const auto &i : g[v])
		brute_dfs(vis, i);
}

int brute() {
	vector<int> vis(n);
	for (int i = 0; i < n; i++) {
		for (auto &x : vis) x = 0;
		for (const auto &j : g[i])
			brute_dfs(vis, j);
		if (vis[i]) return 1;
	}
	return 0;
}

int add_teleporter(int u, int v) {
	if (u < k && v < k) {
		return u >= v;
	}
	g[u].push_back(v);
	grev[v].push_back(u);
	int x = add(0, 0, 0, 0, k - 1, u, v);
	if (OO) {
		int y = brute();
		if (x != y) {
			cout << "difference! " << x << " " << y << '\n';
		}
	}
	return x;
}

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