Submission #290123

#	Time	Username	Problem	Language	Result	Execution time	Memory
290123		tinjyu	Swapping Cities (APIO20_swap)	C++14	100 / 100	440 ms	63612 KiB

swap

#include "swap.h"
#include <iostream>
#include <vector>
using namespace std;
long long int f2[1000005],can=0,fa[1000005][21],deep[1000005],p[1000005],cnt,n,m,deg[1000005],u[1000005],v[1000005],w[1000005],f[1000005],ok[1000005],num[1000005],d[1000005];
int find(int x)
{
	if(x==f2[x])return f2[x];
	return f2[x]=find(f2[x]);
}
void qs(int s,int e)
{
	if(s==e)return ;
	long long int l=s,r=e,mid=w[(s+e)/2];
	while(l<=r)
	{
		while(w[l]<mid)l++;
		while(w[r]>mid)r--;
		if(l<=r)
		{
			swap(w[l],w[r]);
			swap(u[l],u[r]);
			swap(v[l],v[r]);
			l++;
			r--;
		}
	}
	if(r>s)qs(s,r);
	if(e>l)qs(l,e);
}
void update(int x)
{
	if(p[x]!=-1)return ;
	//cout<<x<<" "<<ok[x]<<" "<<f[x]<<endl;
	if(ok[x]==1)
	{
		p[x]=x;
		return ;
	}
	update(f[x]);
	p[x]=p[f[x]];
	return ;
}
void update2(int x)
{
	if(deep[x]!=0)return ;
	if(f[x]==x)
	{
		deep[x]=1;
		return ;
	}
	update2(f[x]);
	deep[x]=deep[f[x]]+1;
	return ;
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n=N;
	m=M;
	cnt=n-1;
	for(int i=0;i<m;i++)
	{
		u[i]=U[i];
		v[i]=V[i];
		w[i]=W[i];
	}
	qs(0,m-1);
	long long int ma=0;
	for(int i=0;i<=1000000;i++)
	{
		f2[i]=i;
		f[i]=i;
	}
	for(int i=0;i<m;i++)
	{
		long long int x=u[i],y=v[i];
		deg[x]++;
		deg[y]++;
		long long int fx=find(x),fy=find(y);
		//cout<<fx<<" "<<fy<<endl;
		if(fx==fy)
		{
			if(ok[fx]==0)
			{
				can=1;
				ok[fx]=1;
				num[fx]=w[i];
			}
		}
		else
		{
			if(ok[fx]==1 || ok[fy]==1 || deg[x]>=3 || deg[y]>=3)
			{
				cnt++;
				//cout<<cnt<<" "<<x<<" "<<y<<endl;
				can=1;
				f[fx]=cnt;
				f[fy]=cnt;
				f2[fx]=cnt;
				f2[fy]=cnt;
				ok[cnt]=1;
				num[cnt]=w[i];
			}
			else
			{
				f[fy]=fx;
				f2[fy]=fx;
			}
		}
	}
	if(can==0)return ;
	for(int i=0;i<=cnt;i++)
	{
		p[i]=-1;
	}
	for(int i=0;i<=cnt;i++)
	{
		if(p[i]==-1)update(i);
		//cout<<i<<" "<<p[i]<<endl;
		//cout<<i<<" "<<f[i]<<endl;
	}
	for(int i=0;i<=cnt;i++)
	{
		if(deep[i]==0)update2(i);
	}

	for(int i=0;i<=cnt;i++)
	{
		fa[i][0]=f[p[i]];
		if(f[p[i]]==p[i])fa[i][0]=-1;
	}
	for(int i=1;i<=20;i++)
	{
		for(int j=0;j<=cnt;j++)
		{
			if(fa[j][i-1]==-1)continue;
			fa[j][i]=fa[fa[j][i-1]][i-1];
		}
	}
	return ;
}
int lca(int x,int y)
{
	if(deep[x]<deep[y])swap(x,y);
	//cout<<x<<" "<<y<<" "<<deep[x]<<" "<<deep[y]<<endl;
	int tmp=deep[x]-deep[y];
	int pp=0;
	while(tmp>0)
	{
		if(tmp%2==1)x=fa[x][pp];
		tmp/=2;
		pp++;
	}
	if(x==y)return num[x];
	for(int i=20;i>=0;i--)
	{

		if(fa[x][i]!=fa[y][i] && fa[x][i]!=-1)
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return num[f[x]];
}
int getMinimumFuelCapacity(int X, int Y) {
	if(can==0)return -1;
	int x=p[X],y=p[Y];
	//cout<<" "<<x<<" "<<y<<endl;
	int ans=lca(x,y);
	if(ans==0)return -1;
	return ans;
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:67:16: warning: unused variable 'ma' [-Wunused-variable]
   67 |  long long int ma=0;
      |                ^~

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