Submission #630442

#TimeUsernameProblemLanguageResultExecution timeMemory
630442Ooops_sorryGame (APIO22_game)C++17
60 / 100
4090 ms42640 KiB
#include<bits/stdc++.h> using namespace std; mt19937 rnd(51); #define ll long long #define pb push_back #define ld long double const int N = 3e5 + 10, INF = 1e9; int n, k, in[N], out[N]; vector<int> g[N], gr[N]; bool cycle = 0; void dfs(int v) { if (v >= k && out[v] <= in[v]) { cycle = 1; } for (auto to : g[v]) { if (in[v] > in[to]) { in[to] = in[v]; dfs(to); } } } void zhfs(int v) { if (v >= k && out[v] <= in[v]) { cycle = 1; } for (auto to : gr[v]) { if (out[v] < out[to]) { out[to] = out[v]; zhfs(to); } } } int add_teleporter(int u, int v) { if (max(u, v) < k) { if (u >= v) { cycle = 1; } } else { g[u].pb(v); gr[v].pb(u); if (in[v] < in[u]) { in[v] = in[u]; dfs(v); } if (out[u] > out[v]) { out[u] = out[v]; zhfs(u); } } return cycle; } void init(int n_, int k_) { n = n_, k = k_; for (int i = 0; i < n; i++) { in[i] = -INF, out[i] = INF; } for (int i = 0; i < k; i++) { in[i] = out[i] = i; if (i + 1 < k) { add_teleporter(i, i + 1); } } } #ifdef LOCAL signed main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // LOCAL ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; vector<pair<int,int>> e(m); for (int i = 0; i < m; i++) { cin >> e[i].first >> e[i].second; } init(n, k); int i; for (i = 0; i < m; i++) { int res = add_teleporter(e[i].first, e[i].second); assert(res == 0 || res == 1); if (res == 1) { break; } } cout << i << endl; return 0; } #endif // LOCAL
#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...