Submission #1022341

#TimeUsernameProblemLanguageResultExecution timeMemory
1022341imarnSwapping Cities (APIO20_swap)C++14
100 / 100
215 ms66296 KiB
#include<bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC target("avx2") #define ll long long #define pii pair<ll,ll> #define pll pair<ll,ll> #define plx pair<ll,int> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define vl vector<ll> #define vvi vector<vi> using namespace std; const int mxn=3e5+5; int pr[mxn]; int up[mxn][20]{0}; int dep[mxn]{0},d[mxn]{0}; vector<int>g[mxn]; int dp[mxn]{0}; bool vis[mxn]{0},ok=0; int get(int r){ return pr[r]==r?r:pr[r]=get(pr[r]); } void dfs(int u,int p,int l){ up[u][0]=p;dep[u]=l; for(int i=1;i<20;i++)up[u][i]=up[up[u][i-1]][i-1]; for(auto v:g[u]){ if(v==p)continue; if(!vis[v])vis[v]=1,dp[v]=dp[u]; dfs(v,u,l+1); } } int get(int a,int b){ if(dep[a]>dep[b])swap(a,b); for(int i=19;i>=0;i--)if(dep[b]-(1<<i)>=dep[a])b=up[b][i]; if(a==b)return a; for(int i=19;i>=0;i--)if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i]; return up[a][0]; } void init(int N,int M,vi U,vi V,vi W){ vector<pair<int,pii>>edge;iota(pr,pr+N,0); for(int i=0;i<M;i++)edge.pb({W[i],{U[i],V[i]}}); sort(edge.begin(),edge.end()); int cr=N-1; for(auto it : edge){ cr++;pr[cr]=cr;dp[cr]=it.f; d[it.s.f]++;d[it.s.s]++; int x=get(it.s.f),y=get(it.s.s); pr[x]=cr;pr[y]=cr; if(x==y){g[cr].pb(x);vis[cr]=1;continue;} g[cr].pb(x);g[cr].pb(y); if(d[it.s.f]>=3||d[it.s.s]>=3||vis[x]||vis[y])vis[cr]=1; }if(!vis[cr])return;ok=1; dfs(cr,cr,0); } int getMinimumFuelCapacity(int X, int Y) { if(!ok)return -1; return dp[get(X,Y)]; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...