Submission #1203296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203296		temporary1	Swapping Cities (APIO20_swap)	C++17	13 / 100	75 ms	11912 KiB

swap

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

#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }

const int MOD = 1e9+7; // 998244353;

vctr<pii> adj[100005];
int d[100005];
int pw[100005];
int pa[100005];
int deg[100005];
int nxt[100005];

struct DSU {
	void init(int n) {
	    fill(pa+1,pa+n+1,-1);
	    fill(nxt+1,nxt+n+1,2e9);
	}

	int root(int x) {
		return pa[x] < 0 ? x : root(pa[x]);
	}

	int unite(int x, int y, int w) {
		int px = root(x);
		int py = root(y);
		if (pa[px] > pa[py])swap(px,py),swap(x,y);
		if (++deg[x] > 2) {
			amin(nxt[px],w);
		}
		if (++deg[y] > 2) {
			amin(nxt[px],w);
		}
		if (px == py) {
			amin(nxt[px],w);
			return -1;
		}
		pa[px] += pa[py];
		pa[py] = px;
		adj[px].eb(py,w);
    	amin(nxt[px],max(w,nxt[py]));
		pw[py] = w;
		return px;
	}
} dsu;

void dfs(int node, int fa) {
	d[node] = d[fa]+1;
	for (auto [it,w] : adj[node]) {
		if (it == fa)continue;
		// cout << node << "->" << it << '\n';
		amin(nxt[it],nxt[node]);
		dfs(it,node);
	}
	return;
}

void init(int n, int m, vctr<int> U, vctr<int> V, vctr<int> W) {
	vctr<tiii> edges;
	for (int i = 0; i < m; ++i) {
		edges.eb(W[i],U[i],V[i]);
	}
	sort(all(edges));
	dsu.init(n);
	for (auto [w,u,v] : edges) {
		++u; ++v;
		// brick(w);brick(u);dbg(v);
		dsu.unite(u,v,w);
	}
	dfs(dsu.root(1),0);
	return;
}

int getMinimumFuelCapacity(int x, int y) {
	++x; ++y;
	int xi = x, yi = y;
	if (d[xi] > d[yi])swap(xi,yi), swap(x,y);
	int prv = 0;
	while (d[xi] < d[yi])prv = yi, yi = pa[yi];
	if (xi == yi) {
		int ans = max(nxt[xi],pw[prv]);
		if (ans == (int)2e9)ans = -1;
		return ans;
	}
	while (pa[xi] != pa[yi])xi = pa[xi], yi = pa[yi];
	int ans = max(nxt[pa[xi]],max(pw[xi],pw[yi]));	
	if (ans == (int)2e9)ans = -1;
	return ans;
}

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