Submission #578324

#TimeUsernameProblemLanguageResultExecution timeMemory
578324handlenameGame (APIO22_game)C++17
2 / 100
9 ms14416 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair const int MOD=1e9+7; int n,k; vector<int> adj[300001],rev[300001]; pair<int,int> range[300001]; //rightmost special node to go i, leftmost special node i can go to void init(int N,int K){ n=N; k=K; for (int i=1;i<=k;i++){ //adj[i].pb(i+1); //rev[i+1].pb(i); range[i]=mp(i,i); } for (int i=k+1;i<=n;i++){ range[i]=mp(0,k+1); } } bool upd(int u,int v){ if (range[u].second<=range[v].first) return false; if (range[u].first>=range[v].second) return true; if (range[u]==range[v]) return false; //u1 u u2 //v1 v v2 //u2>v1 and u1<v2 //if we use u->v edge,v1=max(u1,v1) and u2=min(u2,v2) if ((range[v].first+range[v].second)/2<range[u].first){ range[v].first=(range[v].first+range[v].second)/2+1; for (auto i:adj[v]){ if (upd(v,i)) return true; } } if ((range[u].second+range[u].first)/2>=range[v].second){ range[u].second=(range[u].second+range[u].first)/2; for (auto i:rev[u]){ if (upd(i,u)) return true; } } return false; } int add_teleporter(int u,int v){ u++; v++; if (u>=v && u<=k) return 1; if (u==v) return 0; adj[u].pb(v); rev[v].pb(u); return upd(u,v); }
#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...