Submission #897061

#TimeUsernameProblemLanguageResultExecution timeMemory
897061LitusianoGame (APIO22_game)C++17
2 / 100
1 ms344 KiB
#include<bits/stdc++.h> using namespace std; #include "game.h" int k1,n1; vector<vector<int>> G1,Grev1, DAG; vector<int> reachable0, reachablek; int act = 0; bool ok = 0; void dfs2(int u){ if(reachable0[u]) return; reachable0[u] = 1; if(reachable0[u] + reachablek[u] == 2) ok = 1; // cerr<<"START "<<u<<endl; for(int v : G1[u]) dfs2(v); // cerr<<"END "<<u<<endl; // top.push_back(u); } void dfs3(int u){ if(reachablek[u]) return; reachablek[u] = 1; if(reachable0[u] + reachablek[u] == 2) ok = 1; for(int v : Grev1[u]){ dfs3(v); } // scc[u] = act; } int add_teleporter(int u, int v) { // if(scc.size() && scc[u] == scc[v] && scc[u] > -1) return 0; if(u == v){ if(u < k1) return 1; return 0; } if(max(u,v) < k1){ if(u > v) return 1; return 0; } G1[u].push_back(v); Grev1[v].push_back(u); if(reachable0[u] && !reachable0[v]){ dfs2(v); } if(reachablek[v] && !reachablek[u]){ dfs3(u); } return ok; } void init(int n, int k) { k1 = k; n1 = n; G1.assign(n,vector<int>()); Grev1 = G1; // cerr<<"HERE "<<n<<" "<<k<<endl; reachable0.assign(n,0); reachablek.assign(n,0); ok = 0; reachable0[0] = 1; reachablek[0] = 1; for(int i = 0; i<=k-2; i++){ reachable0[i+1] = reachablek[i+1] = 1; G1[i].push_back(i+1); Grev1[i+1].push_back(i); } }
#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...