Submission #982421

#	Time	Username	Problem	Language	Result	Execution time	Memory
982421		Lib	Swapping Cities (APIO20_swap)	C++14	100 / 100	376 ms	77488 KiB

swap

#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,c;
vector <vector <int> > InComponents;
vector <vector <int> > adj; //the edge list of the KRT
vector <int> TVector;
int RootID; //ID of the root node of the KRT;
struct Edge{
	long long Weight;
	int Start;
	int End;
};
bool operator< (const Edge &x, const Edge &y){
	return x.Weight<y.Weight;
}
Edge Elist[500003];
int Depth[500003];
int Deg[500003];
int CurRep[500003]; //id of the respresentative node on the KRT
int Par[500003]; //Parent of node with id i on the KRT;
int Toggle[500003]; //is the i-th node on the KRT toggled?
int Check[500003];
int Ancestor[500003][25];
int Val[500003];//the value of the i-th node of the KRT
vector <int> KRTID;
int GetRep(int u){
	if(CurRep[u]==-1){
		return u;
	}else{
		return CurRep[u]=GetRep(CurRep[u]);
	}
}
void DSU(int id, int u, int v, int w){
	int CurID=n-1+id;
	Deg[u]++;
	Deg[v]++;
	//u and v belongs to the same component. The component now has a cycle. Immediately toggle the root node of the current 
	//subtree that includes both u and v on the KRT
	//Screw partial, binary tree KRT, opt into full-KRT instead
	int RepU=GetRep(u), RepV=GetRep(v);
	if(RepU==RepV){
		Par[RepU]=CurID;
		Val[CurID]=w;
		adj[RepU].push_back(CurID);
		adj[CurID].push_back(RepU);
		CurRep[RepU]=CurID;
		//The node isn't toggled just yet. Toggle it immediately as there is a cycle
		Toggle[CurID]=1;
	}else{
		//u and v doesn't belong to the same component. Merge them
		int OldComp1=RepU, OldComp2=RepV;
		adj[RepU].push_back(CurID);
		adj[RepV].push_back(CurID);
		adj[CurID].push_back(RepU);
		adj[CurID].push_back(RepV);
		Par[RepU]=CurID;
		Par[RepV]=CurID;
		CurRep[RepU]=CurID;
		CurRep[RepV]=CurID;
		Val[CurID]=w; //if I got WA because I forgot to set the fucking node weight to the nodes on the KRT, I'll shove 3 fingers up my ass.
		//if either of the components are toggled already (having a cycle OR a vertex with degree >=3)
		//OR the merged component has a vertex with degree >3 (either u or v), toggle immediately
		if(Toggle[OldComp1]||Toggle[OldComp2]||Deg[u]>2||Deg[v]>2){
			Toggle[CurID]=1;
		}
	}
	//cout<<CurID<<" ";
}
void init(int N, int M, vector <int> U, vector <int> V, vector <int> W){
	n=N;
	m=M;
	for(int i=0;i<n+m+5;i++){
		adj.push_back(TVector);
	}
	for(int i=1;i<=m;i++){
		Elist[i].Weight=W[i-1];
		Elist[i].Start=U[i-1];
		Elist[i].End=V[i-1];
	}
	sort(Elist+1,Elist+m+1);
	for(int i=0;i<=m+n+1;i++){
		CurRep[i]=-1;
		Par[i]=-1;
		Toggle[i]=0;
	}		
	for(int i=1;i<=m;i++){
		DSU(i,Elist[i].Start,Elist[i].End,Elist[i].Weight);
	}
	//The KRT is now built. BFS from the root node and initialize LCA or something
	deque <int> dq;
	RootID=n+m-1;
	dq.push_back(RootID);
	Check[RootID]=1;
	int Cur;
	while(!dq.empty()){
		Cur=dq.front();
		//cout<<Cur<<" ";
		for(int i=0;i<adj[Cur].size();i++){
			if(!Check[adj[Cur][i]]){
				dq.push_back(adj[Cur][i]);
				Check[adj[Cur][i]]=1;
				Depth[adj[Cur][i]]=Depth[Cur]+1;
			}
		}
		dq.pop_front();
	}
	for(int i=0;i<=20;i++){
		for(int k=0;k<n+m;k++){
			if(i==0){
				Ancestor[k][0]=Par[k];
			}else{
				if(Depth[k]<pow(2,i)){
					Ancestor[k][i]=-1;
				}else{
				Ancestor[k][i]=Ancestor[Ancestor[k][i-1]][i-1];
				}
			}
		}
	}
}
int getMinimumFuelCapacity(int x, int y){
	//I thought that we actually need to use binary lifting to find LCA and then jump from the LCA to find the nearest
	//toggled node on the KRT
	//But apparently small-to-large merging ensures that the depth of the tree is always logN or something, so bruteforcing
	//it is
	//ok nvm this guy is a fucking moron lmao LogN depth my ass. Wrong analysis, wasted 5 minutes. Fuck me
	if(!Toggle[RootID]){
		return -1;
	}
	if(Depth[x]<Depth[y]){
		swap(x,y);
	}

	int JumpLevel=Depth[x]-Depth[y];
	for(int i=19;i>=0;i--){
		if(JumpLevel >> i & 1){
			x=Ancestor[x][i];
		}
	}
	for(int i=20;i>=0;i--){
		if(Ancestor[x][i]!=Ancestor[y][i]){
			x=Ancestor[x][i];
			y=Ancestor[y][i];
		}
	}
	x=Par[x];
	y=Par[y];
	if(Toggle[x]){
		return Val[x];
	}
	for(int i=20;i>=0;i--){
		if(Ancestor[x][i]!=-1&&!Toggle[Ancestor[x][i]]){
			x=Ancestor[x][i];
		}
	}
	x=Par[x];
	if(Toggle[x]&&x!=-1){
		return Val[x];
	}
	return -1;
	
	/*
	while(Depth[x]>Depth[y]){
		x=Par[x];
	}
	if(x==y){
		goto SkipPoint;
	}
	while(x!=y){
		x=Par[x];
		y=Par[y];
	}
	SkipPoint:
	while(!Toggle[x]&&x!=-1){
		x=Par[x];
	}
	if(x!=-1){
		return Val[x];
	}else{
		return -1;
	}
	*/
}
/*
int q;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("swap_12_2.in","r",stdin);
	cin>>n>>m;
	vector <int> U,V,W;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		U.push_back(a);
		V.push_back(b);
		W.push_back(c);
	}
	init(n,m,U,V,W);
	deque <int> dq;
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>a>>b;
		dq.push_back(getMinimumFuelCapacity(a,b));
		cout<<dq.back()<<"\n";
	}
	freopen("swap_12_2.out","r",stdin);
	int cur, score=0;
	for(int i=1;i<=q;i++){
		cin>>cur;
		if(cur==dq.front()){
			score++;
		}else{
			cout<<dq.front()<<" "<<cur<<" "<<Val[RootID]<<"\n";
		}
		dq.pop_front();
	}
	cout<<score<<" "<<q<<" ";
	int maxdepth=0;
	for(int i=0;i<=n+m+5;i++){
		maxdepth=max(maxdepth,Depth[i]);
	}
	//cout<<maxdepth;
}
*/
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
*/

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:98:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int i=0;i<adj[Cur].size();i++){
      |               ~^~~~~~~~~~~~~~~~

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