Submission #1225908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225908		midi	Swapping Cities (APIO20_swap)	C++20	100 / 100	191 ms	51164 KiB

swap

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

typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll,ll> prll;

#define fi first
#define se second
#define sz size
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define all(x) ((x).begin()), ((x).end())

#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)

inline void maxa (ll &a, ll b) { if (a<b) a=b; }
inline void mina (ll &a, ll b) { if (a>b) a=b; }


#define mxN (100'010ll)
#define mxM (200'010ll)
#define lgN (17ll)
#define INF (LLONG_MAX>>3ll)

ll n, m;

struct PUF
{
	vcll par, ct, dt, wei, deg;
	vcb comp;
	inline void bd()
	{
		par.resize(mxN);
		ct.resize(mxN);
		dt.resize(mxN);
		wei.resize(mxN);
		deg.resize(mxN);
		comp.resize(mxN);
		ll u;
		f0r(u,1,n)
		{
			par[u]=u;
			ct[u]=dt[u]=INF;
			wei[u]=1;
			deg[u]=0;
			comp[u]=0;
		}
	}
	ll find (ll u)
	{
		if (par[u]==u) return u;
		return find(par[u]);
	}
	void unite (ll u, ll v, ll w)
	{
		// printf("uniting %lli, %lli, %lli\n", u, v, w);
		deg[u]++;
		deg[v]++;
		bool c = deg[u]>=3 or deg[v]>=3;
		u=find(u);
		v=find(v);
		if (wei[u]<wei[v]) swap(u,v);
		if (u==v)
		{
			// printf("cycle found!\n");
			mina(ct[u],w);
			mina(ct[v],w);
			comp[u]=comp[v]=1;
			return;
		}
		par[v]=u;
		dt[v]=w;
		wei[u]+=wei[v];
		comp[u] = comp[v] = (c or comp[u] or comp[v]);
		if (comp[u])
		{
			// printf("3podo!!!\n");
			mina(ct[u],w);
			mina(ct[v],w);
		}
	}
}puf;

struct edge { ll u, v, w; };
bool cmp (edge &a, edge &b) { return a.w<b.w; }
vc<edge> edges;

ll root;
vcll dep(mxN);
vc<vcll> gr(mxN);
vc<vc<prll>> lift(lgN+2, vc<prll>(mxN));

inline void dfs (ll u=0, ll d=0)
{
	dep[u]=d;
	for (ll v:gr[u]) dfs(v,d+1);
}

inline void bd_tree()
{
	ll k, u;

	// f0r(u,1,n) printf("ct[%lli]: %lli\n", u, puf.ct[u]);

	f0r(u,1,n) if (puf.par[u]==u) root=u;
	puf.par[root]=0;
	gr[0].pb(root);
	f0r(u,1,n)gr[puf.par[u]].pb(u);
	f0r(u,1,n) lift[0][u] = {puf.par[u], puf.dt[u]};
	f0r(k,1,lgN) f0r(u,1,n)
	{
		ll p=lift[k-1][u].fi;
		lift[k][u].fi = lift[k-1][p].fi;
		lift[k][u].se = max(lift[k-1][u].se, lift[k-1][p].se);
	}
	dfs();
}

void init(int N1, int M1, vc<int> U1, vc<int> V1, vc<int> W1)
{
	n=N1; m=M1;
	puf.bd();
	ll i;
	f0r(i,0,m-1)
	{
		edge e;
		e.u=U1[i]+1;
		e.v=V1[i]+1;
		e.w=W1[i];
		edges.pb(e);
	}
	sort(all(edges), cmp);
	for (edge &e:edges) puf.unite(e.u, e.v, e.w);
	bd_tree();
}

ll X, Y;
inline prll mpq (ll u, ll v)
{
	ll mx=-1, k;
	if (dep[u]<dep[v]) swap(u,v);
	r0f(k,lgN,0)
	{
		ll p=lift[k][u].fi, w=lift[k][u].se;
		if (dep[p]>=dep[v])
		{
			u=p;
			maxa(mx,w);
		}
	}
	if (u==v) return {mx,u};

	r0f(k,lgN,0)
	{
		ll p1=lift[k][u].fi, w1=lift[k][u].se;
		ll p2=lift[k][v].fi, w2=lift[k][v].se;
		if (p1!=p2)
		{
			u=p1; v=p2;
			maxa(mx,max(w1,w2));
		}
	}
	maxa(mx, max(lift[0][u].se, lift[0][v].se));

	return {mx,lift[0][u].fi};
}

inline ll find_ct (ll u)
{
	while (puf.par[u]!=u and !puf.comp[u]) u=puf.par[u];
	return puf.ct[u];
}

int getMinimumFuelCapacity(int X1, int Y1)
{
	X=X1+1; Y=Y1+1;
	prll res=mpq(X,Y);
	// printf("root: %lli\n", root);
	// printf("puf.comp[root]: %lli\n", (ll)puf.comp[root]);
	return puf.comp[root] ? max(res.fi, find_ct(res.se)) : -1;
}

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