oj.uz

Submission #982407

# Submission time Handle Problem Language Result Execution time Memory
982407 2024-05-14T08:16:21 Z Lib Swapping Cities (APIO20_swap) C++14
37 / 100
 2000 ms 78348 KB 
#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][20];
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++){
		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]=-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<=19;i++){
		for(int k=0;k<n+m;k++){
			if(i==0){
				Ancestor[k][i]=Par[k];
			}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(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];
		}
	}
	if(x==y){
		goto SkipPoint;
	}
	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];
	}
	for(int i=19;i>=0;i--){
		if(!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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14936 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 14936 KB Output is correct
9 Correct 67 ms 45852 KB Output is correct
10 Correct 96 ms 50724 KB Output is correct
11 Correct 81 ms 50468 KB Output is correct
12 Correct 88 ms 51236 KB Output is correct
13 Correct 81 ms 52000 KB Output is correct
14 Correct 73 ms 45196 KB Output is correct
15 Correct 154 ms 54184 KB Output is correct
16 Correct 157 ms 54220 KB Output is correct
17 Correct 164 ms 55936 KB Output is correct
18 Execution timed out 2071 ms 53572 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14936 KB Output is correct
3 Execution timed out 2024 ms 53444 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14936 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 14936 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 3 ms 15028 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 3 ms 14936 KB Output is correct
13 Correct 2 ms 14784 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 2 ms 14940 KB Output is correct
16 Correct 2 ms 15192 KB Output is correct
17 Correct 2 ms 14940 KB Output is correct
18 Correct 3 ms 15008 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 3 ms 14940 KB Output is correct
21 Correct 3 ms 14940 KB Output is correct
22 Correct 3 ms 14940 KB Output is correct
23 Correct 2 ms 14788 KB Output is correct
24 Correct 3 ms 14940 KB Output is correct
25 Correct 3 ms 14940 KB Output is correct
26 Correct 3 ms 14940 KB Output is correct
27 Correct 3 ms 14940 KB Output is correct
28 Correct 3 ms 14940 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14936 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 2 ms 14936 KB Output is correct
10 Correct 67 ms 45852 KB Output is correct
11 Correct 96 ms 50724 KB Output is correct
12 Correct 81 ms 50468 KB Output is correct
13 Correct 88 ms 51236 KB Output is correct
14 Correct 81 ms 52000 KB Output is correct
15 Correct 3 ms 15028 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Correct 3 ms 14936 KB Output is correct
18 Correct 2 ms 14784 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 2 ms 14940 KB Output is correct
21 Correct 2 ms 15192 KB Output is correct
22 Correct 2 ms 14940 KB Output is correct
23 Correct 3 ms 15008 KB Output is correct
24 Correct 4 ms 14940 KB Output is correct
25 Correct 3 ms 14940 KB Output is correct
26 Correct 3 ms 14940 KB Output is correct
27 Correct 3 ms 14940 KB Output is correct
28 Correct 2 ms 14788 KB Output is correct
29 Correct 3 ms 14940 KB Output is correct
30 Correct 3 ms 14940 KB Output is correct
31 Correct 3 ms 14940 KB Output is correct
32 Correct 3 ms 14940 KB Output is correct
33 Correct 3 ms 14940 KB Output is correct
34 Correct 11 ms 19536 KB Output is correct
35 Correct 98 ms 54544 KB Output is correct
36 Correct 110 ms 55076 KB Output is correct
37 Correct 99 ms 55924 KB Output is correct
38 Correct 114 ms 53692 KB Output is correct
39 Correct 98 ms 55300 KB Output is correct
40 Correct 87 ms 52768 KB Output is correct
41 Correct 103 ms 53356 KB Output is correct
42 Correct 109 ms 55620 KB Output is correct
43 Correct 101 ms 54812 KB Output is correct
44 Correct 96 ms 55336 KB Output is correct
45 Correct 132 ms 59564 KB Output is correct
46 Correct 96 ms 55564 KB Output is correct
47 Correct 107 ms 54364 KB Output is correct
48 Correct 109 ms 54476 KB Output is correct
49 Correct 90 ms 50240 KB Output is correct
50 Correct 67 ms 40792 KB Output is correct
51 Correct 106 ms 56328 KB Output is correct
52 Correct 154 ms 65204 KB Output is correct
53 Correct 177 ms 72432 KB Output is correct
54 Correct 170 ms 78348 KB Output is correct
55 Correct 90 ms 54036 KB Output is correct
56 Correct 165 ms 68964 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14936 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14940 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 14936 KB Output is correct
9 Correct 67 ms 45852 KB Output is correct
10 Correct 96 ms 50724 KB Output is correct
11 Correct 81 ms 50468 KB Output is correct
12 Correct 88 ms 51236 KB Output is correct
13 Correct 81 ms 52000 KB Output is correct
14 Correct 73 ms 45196 KB Output is correct
15 Correct 154 ms 54184 KB Output is correct
16 Correct 157 ms 54220 KB Output is correct
17 Correct 164 ms 55936 KB Output is correct
18 Execution timed out 2071 ms 53572 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14936 KB Output is correct
4 Correct 2 ms 14684 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 2 ms 14936 KB Output is correct
10 Correct 67 ms 45852 KB Output is correct
11 Correct 96 ms 50724 KB Output is correct
12 Correct 81 ms 50468 KB Output is correct
13 Correct 88 ms 51236 KB Output is correct
14 Correct 81 ms 52000 KB Output is correct
15 Correct 73 ms 45196 KB Output is correct
16 Correct 154 ms 54184 KB Output is correct
17 Correct 157 ms 54220 KB Output is correct
18 Correct 164 ms 55936 KB Output is correct
19 Execution timed out 2071 ms 53572 KB Time limit exceeded
20 Halted 0 ms 0 KB -