Submission #1305797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305797		basic	Game (APIO22_game)	C++20	30 / 100	4061 ms	5656 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int vs[303030], n, k;
vector<int> e[303030], re[303030];
void init(int N, int K) {
	n = N, k = K;
	for (int i = 1; i < k; i++)
		e[i - 1].push_back(i), re[i].push_back(i - 1);
}
pair<int, int> dfs(int x, vector<int> e[]) {
	vs[x] = 0;
	pair<int, int> r{1e6, -1e6}, t;
	if (x < k)
		r = {x, x};
	for (int i : e[x])
		if (vs[i])
			t = dfs(i, e), r.first = min(r.first, t.first), r.second = max(r.second, t.second);
	return r;
}
int add_teleporter(int u, int v) {
	e[u].push_back(v), re[v].push_back(u);
	fill(vs, vs + n, 1);
	int x = dfs(u, re).second;
	fill(vs, vs + n, 1);
	return x >= dfs(v, e).first;
}

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