Submission #1223128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223128		boclobanchat	Swapping Cities (APIO20_swap)	C++20	100 / 100	242 ms	58296 KiB

swap

#include"swap.h"
#include<bits/stdc++.h>
using namespace std;
int getlog(long long n) { return 63-__builtin_clzll(n); }
const int MAXN=4e5+5;
struct edge { int l,r,v; };
bool comp(edge a,edge b) { return a.v<b.v; }
int dsu[MAXN],F[MAXN],sp[MAXN][20],pos[MAXN],dis[MAXN],N,rt;
vector<int> vi[MAXN],ds[MAXN];
edge E[MAXN];
pair<int,int> chain[MAXN];
bool del[MAXN];
int root(int i)
{
	if(!dsu[i]) return i;
	return dsu[i]=root(dsu[i]);
}
void merge(int i,int j,int k,int p)
{
	int a=i,b=j;
	if((i=root(i))==(j=root(j)))
	{
		del[i]=true;
		for(auto v:vi[i]) F[v]=k;
		vi[i].clear();
		return ;
	}
	if(vi[i].size()<vi[j].size()) swap(i,j),swap(a,b);
	if(a==chain[i].first) swap(chain[i].first,chain[i].second);
	if(b==chain[j].second) swap(chain[j].first,chain[j].second);
	for(auto v:vi[j]) vi[i].push_back(v);
	dsu[j]=i,del[i]|=del[j]|(!(a==chain[i].second&&chain[j].first==b));
	if(del[i])
	{
		for(auto v:vi[i]) F[v]=k;
		vi[i].clear();
	}
	else chain[i].second=chain[j].second;
	ds[p].push_back(pos[i]),ds[p].push_back(pos[j]),pos[i]=rt=p;
}
void dfs(int i,int pre)
{
	sp[i][0]=pre;
	for(int j=1;j<=19;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
	for(auto v:ds[i])
	{
		dis[v]=dis[i]+1;
		dfs(v,i);
	}
}
int lca(int a,int b)
{
	int x=dis[a],y=dis[b],m=min(x,y);
	for(int i=19;i+1;i--)
	{
		if((x-m)&(1<<i)) a=sp[a][i];
		if((y-m)&(1<<i)) b=sp[b][i];
	}
	if(a==b) return a;
	for(int i=19;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
	return sp[a][0];
}
void init(int n,int m,vector<int> U,vector<int> V,vector<int> W)
{
	N=n;
	for(int i=1;i<=n;i++) vi[i].push_back(i),chain[i]={i,i},pos[i]=i;
	for(int i=1;i<=m;i++) E[i]={U[i-1]+1,V[i-1]+1,W[i-1]};
	sort(E+1,E+m+1,comp);
	for(int i=1;i<=m;i++) merge(E[i].l,E[i].r,i,i+n);
	dfs(rt,rt);
}
int getMinimumFuelCapacity(int x,int y)
{
	x++,y++;
	if(!F[x]&&!F[y]) return -1;
	return E[max(min(F[x],F[y]),lca(x,y)-N)].v;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27