Submission #838778

#TimeUsernameProblemLanguageResultExecution timeMemory
838778arbuzickGame (APIO22_game)C++17
60 / 100
4073 ms40264 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 3e5 + 5; vector<int> g[maxn], _g[maxn]; int mink[maxn], maxk[maxn]; int n, k; void init(int _n, int _k) { n = _n, k = _k; for (int i = 0; i + 1 < k; ++i) { g[i].push_back(i + 1); _g[i + 1].push_back(i); } for (int i = 0; i < k; ++i) { mink[i] = maxk[i] = i; } for (int i = k; i < n; ++i) { mink[i] = k; maxk[i] = -1; } } bool dfs_min(int v, int val) { if (mink[v] <= val || v < k) { return false; } mink[v] = val; if (mink[v] <= maxk[v]) { return true; } for (auto u : _g[v]) { if (dfs_min(u, val)) { return true; } } return false; } bool dfs_max(int v, int val) { if (maxk[v] >= val || v < k) { return false; } maxk[v] = val; if (mink[v] <= maxk[v]) { return true; } for (auto u : g[v]) { if (dfs_max(u, val)) { return true; } } return false; } int add_teleporter(int u, int v) { if (u == v && u < k) { return 1; } if (u > v && u < k) { return 1; } if (u < k && v < k) { return 0; } g[u].push_back(v); _g[v].push_back(u); return dfs_max(v, maxk[u]) || dfs_min(u, mink[v]); } // int main() { // int N, M, K; // cin >> N >> M >> K; // std::vector<int> u(M), v(M); // for (int i = 0; i < M; ++i) { // cin >> u[i] >> v[i]; // } // init(N, K); // int i; // for (i = 0; i < M; ++i) { // int answer = add_teleporter(u[i], v[i]); // if (answer != 0 && answer != 1) { // i = -1; // break; // } else if (answer == 1) { // break; // } // } // cout << i; // 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...