Submission #712993

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