Submission #896994

#TimeUsernameProblemLanguageResultExecution timeMemory
896994LitusianoGame (APIO22_game)C++17
0 / 100
0 ms344 KiB
#include<bits/stdc++.h> using namespace std; #include "game.h" int k1,n1; vector<vector<int>> G,Grev, DAG; vector<int> top,used,scc; int act = 0; void dfs(int u){ if(used[u]) return; used[u] = 1; // cerr<<"START "<<u<<endl; for(int v : G[u]) dfs(v); // cerr<<"END "<<u<<endl; top.push_back(u); } void dfs1(int u){ if(used[u]) return; used[u] = 1; for(int v : Grev[u]){ dfs1(v); } scc[u] = act; } void init(int n, int k) { k1 = k; n1 = n; G.assign(n,vector<int>()); Grev = G; // cerr<<"HERE "<<n<<" "<<k<<endl; for(int i = 0; i<=k-2; i++){ G[i].push_back(i+1); Grev[i+1].push_back(i); } } 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; } G[u].push_back(v); Grev[v].push_back(u); used.assign(n1,0); scc.assign(n1,-1); top.clear(); // cerr<<"STARTING DFS OF EDGE "<<u<<" "<<v<<endl; for(int i = 0; i<n1; i++) dfs(i); // cerr<<"TOP"<<endl; // for(int i : top) cerr<<i<<" "; // cerr<<"END TOP"<<endl; used.assign(n1,0); act = 0; for(int i = top.size()-1; i>=0; i--){ if(!used[top[i]]) act++, scc[top[i]] = act, dfs1(top[i]); } set<int> hv; for(int i = 0; i<k1; i++){ hv.insert(scc[i]); } // cerr<<"STARTING SCC OF EDGE: "<<u<<" "<<v<<endl; // for(int i = 0; i<n1; i++){ // cerr<<"SCC: "<<i<<" "<<scc[i]<<endl; // } // cerr<<endl; if(hv.size() < k1) return 1; for(int i = k1; i<n1; i++){ if(hv.count(scc[i])) return 1; } return 0; }

Compilation message (stderr)

game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:72:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |  if(hv.size() < k1) return 1;
      |     ~~~~~~~~~~^~~~
#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...