Submission #572808

#	Time	Username	Problem	Language	Result	Execution time	Memory
572808		8e7	Game (APIO22_game)	C++17	100 / 100	2676 ms	71840 KiB

game

//Challenge: Accepted
//#define _GLIBCXX_DEBUG 1
#include "game.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 300005
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
const int inf = 1e9;
int in[maxn], out[maxn];
int block[maxn];
vector<int> adj[maxn], rev[maxn];
int N, K;
void init(int n, int k) {
	N = n, K = k;
	for (int i = 0;i < n;i++) {
		in[i] = inf, out[i] = -inf;
		block[i] = 19;
	}
	for (int i = 0;i < k - 1;i++) {
		adj[i].push_back(i + 1);
	}
	for (int i = 0;i < k;i++) {
		in[i] = i, out[i] = i;
		block[i] = 0;
	}
}
bool dfs(int n, int d, int type, vector<int> &add) {
	bool ret = 0;
	if (n >= K && in[n] <= out[n]) return 1;
	if (in[n] / (1<<d) == out[n] / (1<<d) && block[n] > d) {
		block[n] = d;
		add.push_back(n);
	}
	if (type == 0) {
		for (int i:adj[n]) {
			if (block[i] <= d+1 && out[i] / (1<<d) < out[n] / (1<<d)) {
				out[i] = out[n];
				ret |= dfs(i, d, type, add);
			}
		}
	} else {
		for (int i:rev[n]) {
			if (block[i] <= d+1 && in[i] / (1<<d) > in[n] / (1<<d)) {
				in[i] = in[n];
				ret |= dfs(i, d, type, add);
			}
		}
	}
	return ret;
}
bool solve(int u, int v, int d, vector<int> check) {
	if (d < 0) return 0;
	if (block[v] <= d && out[v] / (1<<(d-1)) < out[u] / (1<<(d-1))) {
		check.push_back(v);
	}
	if (block[u] <= d && in[u] / (1<<(d-1)) > in[v] / (1<<(d-1))) {
		check.push_back(u);
	}
	vector<int> rec;
	for (int i:check) {
		for (int j:adj[i]) in[i] = min(in[i], in[j]);
		for (int j:rev[i]) out[i] = max(out[i], out[j]);
		if (dfs(i, d-1, 0, rec) || dfs(i, d-1, 1, rec)) return 1;
	}
	return solve(u, v, d-1, rec);
}
int add_teleporter(int u, int v) {
	if (u < K && v < K) {
		if (u >= v) return 1;
	}
	adj[u].push_back(v);
	rev[v].push_back(u);
	vector<int> tmp;
	int val = solve(u, v, 19, tmp);
	return val;
}

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