Submission #347995

#	Time	Username	Problem	Language	Result	Execution time	Memory
347995		arnold518	Swapping Cities (APIO20_swap)	C++14	37 / 100	2096 ms	8448 KiB

swap

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXM = 2e5;

int N, M;

struct Edge
{
	int u, v, w;
};
Edge E[MAXM+10];

int deg[MAXN+10], val[MAXN+10], cnt[MAXN+10], sz[MAXN+10];

struct UF
{
	int par[MAXN+10];

	void init()
	{
		for(int i=1; i<=N; i++)
		{
			par[i]=i;
		}		
	}

	int Find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=Find(par[x]);
	}
}uf;

void init(int _N, int _M, vector<int> _U, vector<int> _V, vector<int> _W)
{
	N=_N; M=_M;
	for(int i=1; i<=M; i++)
	{
		int u=_U[i-1]+1, v=_V[i-1]+1, w=_W[i-1];
		E[i]={u, v, w};
	}
	sort(E+1, E+M+1, [&](const Edge &p, const Edge &q)
	{
		return p.w<q.w;
	});

}
int getMinimumFuelCapacity(int X, int Y)
{
	X++; Y++;
	uf.init();
	for(int i=1; i<=N; i++)
	{
		deg[i]=0;
		val[i]=0;
		cnt[i]=0;
		sz[i]=1;
	}
	for(int i=1; i<=M; i++)
	{
		int u=E[i].u, v=E[i].v, w=E[i].w;
		deg[u]++; deg[v]++;

		int uu=uf.Find(u), vv=uf.Find(v);

		if(uu==vv)
		{
			val[uu]=max(val[uu], deg[u]);
			val[uu]=max(val[uu], deg[v]);
			cnt[uu]++;
		}
		else
		{
			uf.par[vv]=uu;
			val[uu]=max(val[uu], val[vv]);
			cnt[uu]+=cnt[vv];
			sz[uu]+=sz[vv];
			val[uu]=max(val[uu], deg[u]);
			val[uu]=max(val[uu], deg[v]);
			cnt[uu]++;
		}

		int XX=uf.Find(X), YY=uf.Find(Y);
		if(XX!=YY) continue;
		if(val[XX]>=3) return w;
		if(val[XX]==2 && cnt[XX]==sz[XX]) return w;
	}
	return -1;
}

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