이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#include <bits/stdc++.h>
int n, k;
constexpr int N = 3e5 + 5;
int can_reach[N]; // can_reach from k -> 0
int be_reached[N]; // be reached from 0 -> k
std::vector<int> adj[N];
std::vector<int> radj[N];
void add_edge(int u, int v) {
adj[u].push_back(v);
radj[v].push_back(u);
}
void init(int _n, int _k) {
n = _n, k = _k;
for (int i = 0; i < k; i++) {
can_reach[i] = i; // it can reach i -> k - 1
be_reached[i] = i + 1; // can be reach from 0 -> i
}
for (int i = k; i < n; i++) {
can_reach[i] = k; // can't reach any
be_reached[i] = 0; // can't be reached by any
}
for (int i = 0; i + 1 < k; i++) {
add_edge(i, i + 1);
}
}
void update_can_reach(int u, int val) {
if (can_reach[u] <= val) { // reach from can_reach[u] -> k - 1
return; // we don't care
}
can_reach[u] = val;
for (int v : radj[u]) {
update_can_reach(v, val);
}
}
void update_be_reached(int u, int val) {
if (be_reached[u] >= val) { // can be reached from 0 -> be_reached - 1
return;
}
be_reached[u] = val;
for (int v : adj[u]) {
update_be_reached(v, val);
}
}
int add_teleporter(int u, int v) {
if (can_reach[v] < be_reached[u]) {
return 1;
}
update_can_reach(u, can_reach[v]);
update_be_reached(v, be_reached[u]);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |