Submission #713000

#TimeUsernameProblemLanguageResultExecution timeMemory
713000piOOEGame (APIO22_game)C++17
60 / 100
4027 ms59468 KiB
#include "game.h" #include <bits/stdc++.h> constexpr int N = 3e5 + 7, B = 8, inf = 1e9 + 7; int fromMe[N], toMe[N], Mid[N], save[N][2], n, k; //smallest from me, biggest to me std::vector<int> adj[N], rev[N]; bool found = false; void relax(int v) { if (v >= k && fromMe[v] <= toMe[v]) { found = true; } Mid[v] = (fromMe[v] + toMe[v]) >> 1; } void init(int n, int k) { ::n = n, ::k = k; for (int i = 0; i < n; ++i) { if (i >= k) { fromMe[i] = k, toMe[i] = -1; } else { fromMe[i] = toMe[i] = i; } save[i][0] = inf, save[i][1] = -inf; relax(i); } } void dfs2(int v, int x); void dfs1(int v, int x) { if (found || v < k || fromMe[v] <= x) { return; } if (Mid[v] + 50 < x) { save[v][0] = std::min(save[v][0], x); return; } fromMe[v] = x; relax(v); for (int to : rev[v]) { dfs1(to, x); } dfs2(v, save[v][1]); } void dfs2(int v, int x) { if (found || v < k || toMe[v] >= x) { return; } if (Mid[v] - 50 > x) { save[v][1] = std::max(save[v][1], x); return; } toMe[v] = x; relax(v); for (int to : adj[v]) { dfs2(to, x); } dfs1(v, save[v][0]); } int add_teleporter(int u, int v) { if (u < k && v < k && u >= v) { return 1; } adj[u].push_back(v); rev[v].push_back(u); dfs1(u, fromMe[v]); dfs2(v, toMe[u]); return found; }
#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...