Submission #434558

#	Time	Username	Problem	Language	Result	Execution time	Memory
434558		dqhungdl	Swapping Cities (APIO20_swap)	C++17	100 / 100	284 ms	24232 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int MAX=1e5+5;
int P[MAX];
bool isLine[MAX];
ii segs[MAX];
vector<int> S[MAX];
vector<iii> edges;
vector<ii> history[MAX];

int find(int u) {
	if(P[u]==u)
		return u;
	return P[u]=find(P[u]);
}

ii getNewSeg(ii s1,ii s2,int u,int v) {
	if(s1.first==u) {
		if(s2.first==v)
			return {s1.second,s2.second};
		if(s2.second==v)
			return {s1.second,s2.first};
	} else if(s1.second==u) {
		if(s2.first==v)
			return {s1.first,s2.second};
		if(s2.second==v)
			return {s1.first,s2.first};
	}
	return {-1,-1};
}

void merge(int u,int v,int w,int rootU,int rootV) {
	if(S[u].size()<S[v].size()) {
		swap(u,v);
		swap(rootU,rootV);
	}
	P[v]=u;
	segs[u]=getNewSeg(segs[u],segs[v],rootU,rootV);
	bool newIsLine=(segs[u].first!=-1);
	if(isLine[u]!=newIsLine) {
		isLine[u]=false;
		for(int tmp:S[u])
			history[tmp].push_back({w,u});
	}
	while(S[v].size()>0) {
		int tmp=S[v].back();
		S[v].pop_back();
		S[u].push_back(tmp);
		if(!newIsLine)
			history[tmp].push_back({w,u});
	}
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	for(int i=0;i<M;i++)
		edges.push_back({W[i],{U[i],V[i]}});
	sort(edges.begin(),edges.end());
	for(int i=0;i<N;i++) {
		P[i]=i;
		isLine[i]=true;
		segs[i]={i,i};
		S[i].push_back(i);
	}
	for(iii edge:edges) {
		int u=find(edge.second.first),v=find(edge.second.second),w=edge.first;
		if(u!=v)
			merge(u,v,w,edge.second.first,edge.second.second);
		else if(isLine[u]) {
			isLine[u]=false;
			segs[u]={-1,-1};
			for(int tmp:S[u])
				history[tmp].push_back({w,u});
		}
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	vector<ii> hisX=history[X],hisY=history[Y];
	int rs=-1;
	while(hisX.size()>0&&hisY.size()>0&&hisX.back().second==hisY.back().second) {
		rs=max(hisX.back().first,hisY.back().first);
		hisX.pop_back(),hisY.pop_back();
	}
	return rs;
}

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