oj.uz

Submission #982044

# Submission time Handle Problem Language Result Execution time Memory
982044 2024-05-13T18:17:31 Z Lib Swapping Cities (APIO20_swap) C++14
0 / 100
 188 ms 60908 KB 
#include <bits/stdc++.h>
using namespace std;
int n,m;
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][20];
long long Val[500003];//the value of the i-th node of the KRT
vector <int> KRTID;
int GetRep(int u){
	if(CurRep[u]==u){
		return u;
	}else{
		return CurRep[u]=GetRep(CurRep[u]);
	}
}
void DSU(int id, int u, int v, int w){
	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
	int RepU=GetRep(u), RepV=GetRep(v);
	if(RepU==RepV){
		//The node isn't toggled just yet. Toggle it immediately
		if(!Toggle[RepU]){
			Toggle[RepU]=1;
			Val[RepU]=w;
		}else{
		//The node is already toggled by an edge with lower edge. Only a fucking dumbass would touch it - already minimized
		//toggle value. Just leave it alone
		}
	}else{
		//u and v doesn't belong to the same component. Merge them
		int CurID=n-1+id;
		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;
		//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;
		}
		KRTID.push_back(CurID);
		RootID=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++){
		InComponents.push_back(TVector);
		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]=i;
	}		
	for(int i=0;i<n;i++){
		CurRep[i]=i;
		InComponents[i].push_back(i);
		KRTID.push_back(i);
	}
	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;
	dq.push_back(RootID);
	Check[RootID]=1;
	int Cur;
	while(!dq.empty()){
		Cur=dq.front();
		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();
	}
	Par[RootID]=500000;
	Par[500000]=500000;
	Toggle[500000]=1;
	for(int i=0;i<=19;i++){
		for(int k=0;k<KRTID.size();k++){
			if(i==0){
				Ancestor[KRTID[k]][i]=Par[KRTID[k]];
			}else{
				Ancestor[KRTID[k]][i]=Ancestor[Ancestor[KRTID[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(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=19;i>=0;i--){
		if(Ancestor[x][i]!=Ancestor[y][i]){
			x=Ancestor[x][i];
			y=Ancestor[y][i];
		}
	}
	x=Par[x];
	y=Par[y];
	SkipPoint:;
	if(Toggle[x]){
		return Val[x];
	}
	/*int cnt=0;
	while(!Toggle[Par[x]]&&Par[x]!=500000){
		x=Par[x];
	}*/
	for(int i=19;i>=0;i--){
		if(!Toggle[Ancestor[x][i]]){
			x=Ancestor[x][i];
		}
	}
	x=Par[x];
	if(Toggle[x]&&x!=500000){
		return Val[x];
	}
	return -1;
}

Compilation message

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++){
      |               ~^~~~~~~~~~~~~~~~
swap.cpp:111:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for(int k=0;k<KRTID.size();k++){
      |               ~^~~~~~~~~~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:144:2: warning: label 'SkipPoint' defined but not used [-Wunused-label]
  144 |  SkipPoint:;
      |  ^~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 69 ms 47520 KB Output is correct
10 Correct 112 ms 57776 KB Output is correct
11 Correct 91 ms 56280 KB Output is correct
12 Correct 108 ms 58152 KB Output is correct
13 Correct 98 ms 55948 KB Output is correct
14 Correct 90 ms 47728 KB Output is correct
15 Correct 171 ms 59308 KB Output is correct
16 Correct 173 ms 56584 KB Output is correct
17 Correct 188 ms 60804 KB Output is correct
18 Correct 171 ms 60908 KB Output is correct
19 Incorrect 74 ms 24572 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Incorrect 153 ms 59808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Incorrect 2 ms 12636 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 2 ms 12636 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 69 ms 47520 KB Output is correct
10 Correct 112 ms 57776 KB Output is correct
11 Correct 91 ms 56280 KB Output is correct
12 Correct 108 ms 58152 KB Output is correct
13 Correct 98 ms 55948 KB Output is correct
14 Correct 90 ms 47728 KB Output is correct
15 Correct 171 ms 59308 KB Output is correct
16 Correct 173 ms 56584 KB Output is correct
17 Correct 188 ms 60804 KB Output is correct
18 Correct 171 ms 60908 KB Output is correct
19 Incorrect 153 ms 59808 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -