Submission #983045

#TimeUsernameProblemLanguageResultExecution timeMemory
983045Faisal_SaqibGame (APIO22_game)C++17
30 / 100
4038 ms6836 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define vll vector<ll> int n,k; const int N=3e4+10; vector<int> adj[N]; void init(int Q, int P) { n=Q; k=P; for(int i=0;(i+1)<k;i++) adj[i].push_back(i+1); } bool cycle=0; vector<int> path; int vis[N]; bool have[N]; int cur=1; void dfs(int x,int p=-1) { path.push_back(x); have[x]=1; vis[x]=cur; for(auto y:adj[x]) { if(vis[y]==0) // Never visited in any other dfs { dfs(y,x); if(cycle) return; } else if(vis[y]==cur and have[y]){ // Visited in this dfs but cycle is not guranteed vll ex={y}; while(path.back()!=y) { ex.pb(path.back()); path.pop_back(); } if(path.size()==0) { exit(-10); } for(auto lp:ex) { if(lp<k) { cycle=1; return; } } while(ex.size()) { path.pb(ex.back()); ex.pop_back(); } } else{// Visited in other dfs but it will not make a cycle // bcz if it would there would be a path from there to current node but if a path existed then we would have visited this vertex in the same dfs } } path.pop_back(); have[x]=0; } int add_teleporter(int u, int v) { adj[u].push_back(v); memset(vis,0,sizeof(vis)); cur=1; for(int sp=0;sp<k;sp++) { if(!vis[sp]) { path.clear(); cycle=0; dfs(sp); if(cycle) { return 1; } cur++; } } 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...