Submission #584553

#TimeUsernameProblemLanguageResultExecution timeMemory
584553ponkungGame (APIO22_game)C++17
60 / 100
4042 ms17820 KiB
#include "game.h" #include<bits/stdc++.h> using namespace std; #define pb push_back int mx[300005],n,m,mn[300005],u,val,type; vector<int> g[300005],rev[300005]; queue<int> q; void init(int N, int M) { n=N; m=M; for(int i=1;i<=n;i++) { mx[i]=-1e9; mn[i]=1e9; } for(int i=1;i<=m;i++)mx[i]=i,mn[i]=i; } int add_teleporter(int x, int y) { x+=1; y+=1; g[x].pb(y); rev[y].pb(x); if(x>=y&&x>=1&&x<=m&&y>=1&&y<=m)return 1; mn[x]=min(mn[x],mn[y]); val=mn[y]; q.push(x); while(!q.empty()) { u=q.front(); q.pop(); for(auto node:rev[u]) { if(val<mn[node]) { mn[node]=val; q.push(val); } } } mx[y]=max(mx[y],mx[x]); val=mx[x]; q.push(y); while(!q.empty()) { u=q.front(); q.pop(); for(auto node:g[u]) { if(val>mx[node]) { mx[node]=val; q.push(node); } } } type=0; for(int i=m+1;i<=n;i++) { if(mx[i]>=mn[i]) { type=1; } } return type; }
#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...