제출 #963459

#제출 시각아이디문제언어결과실행 시간메모리
963459kilkuwu게임 (APIO22_game)C++17
2 / 100
4 ms14936 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...