Submission #563723

#	Time	Username	Problem	Language	Result	Execution time	Memory
563723		8e7	Swapping Cities (APIO20_swap)	C++17	37 / 100	2098 ms	23372 KiB

swap

//Challenge: Accepted
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct edge{
	int u, v, w;
	edge(){u = v = w = 0;}
	edge(int a, int b, int c){u = a, v = b, w = c;}
};
vector<pii> ev[maxn]; //events
int valid[maxn];
struct DSU{
	int par[maxn], deg[maxn];
	bool mark[maxn];
	pii leaf[maxn];
	int ti;
	void init(int n) {
		for (int i = 0;i < n;i++) {
			ev[i].push_back({-1, i});
			par[i] = i, deg[i] = 0, mark[i] = 0, leaf[i] = {i, 0}; 
			valid[i] = 1<<30;
		}
		ti = 0;
	}
	int find(int a) {
		if (a == par[a]) return a;
		int ret = find(par[a]);
		if (ret != par[a]) ev[a].push_back({ti, ret});
		par[a] = ret;
		return ret;
	}
	void Union(int a, int b) {
		int pa = find(a), pb = find(b);
		deg[a]++, deg[b]++;
		if (deg[a] >= 3 || deg[b] >= 3 || mark[pa]) {
			valid[pb] = min(valid[pb], ti);
			mark[pb] = 1;
		}
		if (deg[a] == 1 && deg[b] == 1) {
			leaf[pb] = {a, b};
		} else {
			if (pa == pb && (leaf[pa] == make_pair(a, b) || leaf[pa] == make_pair(b, a))) {
				valid[pb] = min(valid[pb], ti);
				mark[pb] = 1;
			}
			if (pa != pb) {
				pii p;
				if (deg[leaf[pa].ff] == 1) p.ff = leaf[pa].ff;
				else p.ff = leaf[pa].ss;
				if (deg[leaf[pb].ff] == 1) p.ss = leaf[pb].ff;
				else p.ss = leaf[pb].ss;
				leaf[pb] = p;
			}
		}
		ev[pa].push_back({ti, pb});
		par[pa] = pb;
	}
} d;
vector<edge> ed;
int n, m;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N, m = M;
	for (int i = 0;i < m;i++) ed.push_back(edge(U[i], V[i], W[i]));
	sort(ed.begin(), ed.end(), [&] (edge x, edge y){return x.w < y.w;});
	d.init(n);
	for (int i = 0;i < m;i++) {
		d.Union(ed[i].u, ed[i].v);
		d.ti++;
	}
}
int pfind(int a, int ti) {
	int ind = upper_bound(ev[a].begin(), ev[a].end(), make_pair(ti, 1<<30)) - ev[a].begin() - 1;	
	if (ev[a][ind].ss == a) return a;
	return pfind(ev[a][ind].ss, ti);
}
int getMinimumFuelCapacity(int X, int Y) {
	int low = 0, up = m;
	while (low < up - 1) {
		int mid = (low + up) / 2;
		int vx = pfind(X, mid), vy = pfind(Y, mid);
		if (vx == vy && valid[vx] <= mid) up = mid;
		else low = mid;
	}
	if (up == m) return -1;
	else return ed[up].w;
}

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