oj.uz

Submission #577037

# Submission time Handle Problem Language Result Execution time Memory
577037 2022-06-13T23:08:59 Z Noam527 Game (APIO22_game) C++17
0 / 100
 0 ms 208 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer[1]
2 Halted 0 ms 0 KB -