Submission #1305720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305720		coolboy19521	Swapping Cities (APIO20_swap)	C++20	100 / 100	177 ms	30180 KiB

swap

#include "swap.h"
#include "bits/stdc++.h"

#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)

using namespace std;

const int mxn=1e5+20,mxm=2e5+20,inf=0x3f3f3f3f;

int deg[mxm];

struct{
	vector<pair<int,int>>vp[mxn];
	vector<int>cmp[mxn];
	int ar[mxn],when[mxn];
	void init(int n){
		iota(ar,ar+n,0);
		F0R(i,n)cmp[i].push_back(i);
		memset(when,0x3f,sizeof(when));
	}
	void unite(array<int,3>&eg){
		deg[eg[1]]++,deg[eg[2]]++;
		int u=ar[eg[1]],v=ar[eg[2]];
		if(u==v){
			when[u]=min(when[u],eg[0]);
			return;
		}
		if(cmp[u].size()<cmp[v].size())swap(u,v);
		for(int i:cmp[v]){
			cmp[u].push_back(i);
			ar[i]=u;
			vp[i].emplace_back(u,eg[0]);
		}
		cmp[v].clear();
		if(when[v]!=inf)when[u]=min(when[u],eg[0]);
		if(deg[eg[1]]>=3 or deg[eg[2]]>=3)when[u]=min(when[u],eg[0]);
	}
}dsu;

void init(int N,int M,vector<int>U,vector<int>V,vector<int>W) {
	dsu.init(N);
	vector<array<int,3>>v;
	F0R(i,M)v.push_back({W[i],U[i],V[i]});
	sort(begin(v),end(v));
	for(auto&eg:v)dsu.unite(eg);
}

int getMinimumFuelCapacity(int X,int Y) {
	if(dsu.when[dsu.ar[X]]==inf)return -1;
	int u=X,v=Y,a=0,b=0,ans=0;
	while(u!=v or dsu.when[u]==inf){
		if(a==dsu.vp[X].size() or (b!=dsu.vp[Y].size() and dsu.vp[X][a].second>dsu.vp[Y][b].second))
			v=dsu.vp[Y][b].first,ans=dsu.vp[Y][b++].second;
		else u=dsu.vp[X][a].first,ans=dsu.vp[X][a++].second;
	}
	return max(ans,dsu.when[u]);
}

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