제출 #642557

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
642557		ymm	자매 도시 (APIO20_swap)	C++17	100 / 100	176 ms	24348 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200010;
const int inf = 2e9;
const int lg = 18;
int par[N];
int parw[N];
int sz[N];
int tim[N];
bool pleaf[N];
bool proot[N];
vector<int> A[N];

int root (int v) { return par[v] == -1? v: root(par[v]); }
void unite(int v, int u, int w)
{
	int v0 = v, u0 = u;
	v = root(v);
	u = root(u);
	if (v == u) {
		proot[v] = false;
		tim[v] = min(tim[v], w);
		return;
	}
	if (sz[v] < sz[u]) {
		swap(v, u);
		swap(v0, u0);
	}
	par[u] = v;
	parw[u] = w;
	A[v].push_back(u);
	sz[v] += sz[u];
	if (!proot[v] || !proot[u] || !pleaf[v0] || !pleaf[u0]) {
		proot[v] = false;
		tim[v] = min(tim[v], w);
	}
	if (sz[v] - sz[u] != 1)
		pleaf[v0] = false;
	if (sz[u] != 1)
		pleaf[u0] = false;
}

void init(int n, int m,
          std::vector<int> u, std::vector<int> v, std::vector<int> w) {
	vector<pair<int,pii>> vec;
	Loop (i,0,m)
		vec.push_back({w[i],{v[i],u[i]}});
	fill(par, par+N, -1);
	fill(sz, sz+N, 1);
	fill(tim, tim+N, inf);
	fill(proot, proot+N, true);
	fill(pleaf, pleaf+N, true);
	sort(vec.begin(), vec.end());
	for (auto dard : vec)
		unite(dard.second.first, dard.second.second, dard.first);
}

int height(int v)
{
	int ans = 0;
	while (par[v] != -1) {
		++ans;
		v = par[v];
	}
	return ans;
}

int getMinimumFuelCapacity(int x, int y) {
	int diff = height(y) - height(x);
	int w = 0;
	while (diff > 0) {
		w = max(w, parw[y]);
		y = par[y];
		--diff;
	}
	while (diff < 0) {
		w = max(w, parw[x]);
		x = par[x];
		++diff;
	}
	while (x != y) {
		w = max(w, parw[x]);
		w = max(w, parw[y]);
		x = par[x];
		y = par[y];
	}
	int t = tim[x];
	while (par[x] != -1) {
		t = min(t, max(parw[x], tim[par[x]]));
		x = par[x];
	}
	w = max(w, t);
	return w == inf? -1: w;
}

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