Submission #936971

#	Time	Username	Problem	Language	Result	Execution time	Memory
936971		pan	Swapping Cities (APIO20_swap)	C++17	100 / 100	621 ms	54464 KiB

swap

#include"swap.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
// general
ll const MXN = 100005;
ll const INF = 1e13;
ll n, m;
vector<pii> edgeslist;
bool compare(pii a, pii b)
{
	return a.f<b.f;
}

// persistent UFDS with union by rank
vector<pi> par[MXN], siz[MXN], mxdeg[MXN], cntedge[MXN];
ll deg[MXN];
ll timetravel(vector<pi>& arr, ll time)
{
	ll ind = ub(arr.begin(), arr.end(), mp(time, INF))-arr.begin()-1;
	return arr[ind].s;
}

ll find(ll node, ll time)
{
	ll p = timetravel(par[node], time);
	return (p!=node)?find(p, time):p;
}

void unite(ll x, ll y, ll t)
{
	deg[x]++; deg[y]++;
	ll px = find(x,t), py = find(y, t);
	if (px==py)
	{
		mxdeg[px].pb(mp(t, max(mxdeg[px].back().s, max(deg[x], deg[y]))));
		cntedge[px].pb(mp(t, cntedge[px].back().s+1));
	}
	else
	{
		if (siz[px].back().s<siz[py].back().s) swap(px, py);
		par[py].pb(mp(t, px));
		siz[px].pb(mp(t, siz[px].back().s+siz[py].back().s));
		mxdeg[px].pb(mp(t, max(max(mxdeg[px].back().s, mxdeg[py].back().s), max(deg[x], deg[y]))));
		cntedge[px].pb(mp(t, cntedge[px].back().s+1 +cntedge[py].back().s ));
	}
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
	n =N, m=M;
	for (ll i=0; i<n; ++i)
	{
		par[i].pb(mp(-1, i));
		siz[i].pb(mp(-1, 1));
		mxdeg[i].pb(mp(-1, 0));
		cntedge[i].pb(mp(-1, 0));
		deg[i] = 0;
	}
	edgeslist.resize(m);
	for (ll i=0; i<m; ++i) edgeslist[i] = mp(W[i], mp(U[i], V[i]));
	sort(edgeslist.begin(), edgeslist.end(), compare);
	ll time = -1;
	for (pii e: edgeslist) unite(e.s.f, e.s.s, ++time);
}

int getMinimumFuelCapacity(int X, int Y)
{
	ll x = X, y= Y, lo = 0, hi = m;
	while (lo!=hi)
	{
		ll mid = (lo+hi)/2;
		ll px = find(x, mid), py = find(y, mid);
		if ((px==py) && ((timetravel(mxdeg[px], mid)>2) || (timetravel(cntedge[px], mid)>timetravel(siz[px], mid)-1))) hi = mid;
		else lo = mid+1;
	}
	return (lo==m)?-1: edgeslist[lo].f;
}

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