Submission #1197611

#TimeUsernameProblemLanguageResultExecution timeMemory
1197611MalixSwapping Cities (APIO20_swap)C++20
100 / 100
501 ms81616 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; int n,k,v1=1,v2=1,pos; vii p,X,q; vector<vector<pi>> a; vi low,num,par,sw,cnt,d,Y; bool flag=0; void dfs(int x){ num[x]=v1++; for(auto u:a[x])if(p[x][0]!=u.F){ p[u.F][0]=x; X[u.F][0]=u.S; dfs(u.F); } low[x]=v2++; } int parent(int x){ if(par[x]==x)return x; else return par[x]=parent(par[x]); } bool merge(int x,int y,int w){ int xt=x,yt=y; x=parent(x); y=parent(y); if(x==y){ par[x]=pos; sw[pos]=1; q[x][0]=pos; Y[pos]=w; pos++; return 0; } par[x]=pos;par[y]=pos; cnt[xt]++;cnt[yt]++; q[x][0]=pos;q[y][0]=pos; Y[pos]=w; if(cnt[xt]>=3||cnt[yt]>=3||sw[x]||sw[y])sw[pos]=1; pos++; return 1; } void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) { n=N; k=log2(n+M)+1; low.resize(n,0);num.resize(n,0); p.resize(n,vi(k,-1)); X.resize(n,vi(k,0)); a.resize(n); sw.resize(N+M,0);d.resize(n+M,0); par.resize(N+M);q.resize(N+M,vi(k,-1));Y.resize(N+M,inf); REP(i,0,N+M)par[i]=i; cnt.resize(n,0); priority_queue<ti,vector<ti>,greater<ti>> pq; REP(i,0,M)pq.push({W[i],U[i],V[i]}); pos=n; while(!pq.empty()){ int x=get<0>(pq.top()); int y=get<1>(pq.top()); int z=get<2>(pq.top()); pq.pop(); if(merge(y,z,x)){ a[y].PB({z,x}); a[z].PB({y,x}); } } dfs(0); REP(j,1,k)REP(i,0,n)if(p[i][j-1]!=-1){ p[i][j]=p[p[i][j-1]][j-1]; X[i][j]=max(X[i][j-1],X[p[i][j-1]][j-1]); } REP(j,1,k)REP(i,0,n+M)if(q[i][j-1]!=-1)q[i][j]=q[q[i][j-1]][j-1]; if(sw[n+M-1]==0)flag=1; for(int i=n+M-2;i>=0;i--)d[i]=d[q[i][0]]+1; } bool ances(int x,int y){ if(y==-1)return 1; if(x==-1)return 0; return (num[y]<=num[x]&&low[y]>=low[x]); } int solve(int x,int y){ if(d[x]<d[y])swap(x,y); for(int i=k-1;i>=0;i--)if(q[x][i]!=-1&&d[q[x][i]]>=d[y])x=q[x][i]; for(int i=k-1;i>=0;i--)if(q[x][i]!=q[y][i]){ x=q[x][i]; y=q[y][i]; } x=q[x][0]; y=q[y][0]; if(sw[x])return Y[x]; for(int i=k-1;i>=0;i--)if(q[x][i]!=-1&&sw[q[x][i]]==0)x=q[x][i]; x=q[x][0]; return Y[x]; } int getMinimumFuelCapacity(int x, int y) { if(flag)return -1; int ans=0,ans2=solve(x,y); for(int i=k-1;i>=0;i--)if(!ances(y,p[x][i])){ ans=max(ans,X[x][i]); x=p[x][i]; } for(int i=k-1;i>=0;i--)if(!ances(x,p[y][i])){ ans=max(ans,X[y][i]); y=p[y][i]; } if(ances(y,x))swap(x,y); ans=max(ans,X[x][0]); if(!ances(x,y))ans=max(ans,X[y][0]); return max(ans,ans2); }
#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...