Submission #981185

#	Time	Username	Problem	Language	Result	Execution time	Memory
981185		Lib	Swapping Cities (APIO20_swap)	C++14	0 / 100	1 ms	8536 KiB

swap

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector <vector <int> > InComponents;
vector <int> TVector;
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?
long long Val[500003];//the value of the i-th node of the KRT
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
	if(CurRep[u]==CurRep[v]){
		//The node isn't toggled just yet. Toggle it immediately
		if(!Toggle[CurRep[u]]){
			Toggle[CurRep[u]]=1;
			Val[CurRep[u]]=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=CurRep[u], OldComp2=CurRep[v];
		Par[CurRep[u]]=CurID;
		Par[CurRep[v]]=CurID;
		if(InComponents[u].size()>InComponents[v].size()){
			swap(u,v);
			//Small to large merging
		}
		for(int i=0;i<InComponents[u].size();i++){
			InComponents[CurID].push_back(InComponents[u][i]);
			CurRep[InComponents[u][i]]=CurID;
		}
		for(int i=0;i<InComponents[v].size();i++){
			InComponents[CurID].push_back(InComponents[v][i]);
			CurRep[InComponents[v][i]]=CurID;
		}
		Val[CurID]=w;
		//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;
		}
	}
}
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);
	}
	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<n;i++){
		CurRep[i]=i;
		InComponents[i].push_back(i);
	}
	for(int i=1;i<=m;i++){
		DSU(i,Elist[i].Start,Elist[i].End,Elist[i].Weight);
	}
}

int getMinimumFuelCapacity(int x, int y){
	return 1;
}

Compilation message (stderr)

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

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