제출 #568587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568587		_karan_gandhi	Swapping Cities (APIO20_swap)	C++17	7 / 100	537 ms	51280 KiB

swap

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

#define ll long long
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

int n, m;
// vector<int> _u, _v, w;
vector<int> dp, dep;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> jumpNode, jumpMax;
const int LOG = 20;
int inf = 1e9 + 7;

void dfs(int u, int par, int wt) {
	if (u != par) dep[u] = dep[par] + 1;
	else dep[u] = 0;

	jumpNode[u][0] = par;
	if (wt != -1) jumpMax[u][0] = wt;

	if (adj[u].size() >= 3) {
		priority_queue<int> best;
		for (auto [_, _wt] : adj[u]) best.push(-_wt);
		best.pop();
		best.pop();
		dp[u] = -best.top();
		// cout << pl(best.top()) << endl;
	}

	for (auto [v, _wt] : adj[u]) {
		if (v == par) continue;

		dfs(v, u, _wt);
	}

	for (auto [v, _] : adj[u]) {
		if (v == par) continue;
		dp[u] = min(dp[u], max(dp[v], _));
		dp[v] = min(dp[v], max(dp[u], _));
	}
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	// solve the tree case
	// get the max on the path from u to v <- log(n)
	n = N;
	m = M;
	assert(m == n - 1); // just the tree case

	dp = vector<int>(n, inf);
	// dp.resize(n);
	adj.resize(n);
	dep.resize(n);

	jumpNode = vector<vector<int>>(n, vector<int>(LOG));
	jumpMax = vector<vector<int>>(n, vector<int>(LOG));

	for (int i = 0; i < m; i++) {
		adj[U[i]].emplace_back(V[i], W[i]);
		adj[V[i]].emplace_back(U[i], W[i]);
	}

	dfs(0, 0, -1);

	for (int i = 1; i < LOG; i++) {
		for (int j = 0; j < n; j++) {
			jumpNode[j][i] = jumpNode[jumpNode[j][i - 1]][i - 1];
			jumpMax[j][i] = max(jumpMax[j][i - 1], jumpMax[jumpNode[j][i - 1]][i - 1]);
		}
	}

	// for (auto i : jumpMax) {
	// 	cout << i << endl;
	// }
}

pair<int, int> kth(int a, int k) {
	int res = 0;
	int pow = LOG - 1;
	while (k > 0) {
		if (k < (1 << pow)) pow--;
		res = max(res, jumpMax[a][pow]);
		a = jumpNode[a][pow];

		k -= (1 << k);
	}

	return make_pair(a, res);
}

int get_cost(int a, int b) {
	int res = 0;

	if (dep[a] < dep[b]) {
		swap(a, b);
	}

	pair<int, int> rres = kth(a, dep[a] - dep[b]);
	res = rres.second;
	a = rres.first;
	int pow = LOG - 1;
	// cout << pl(a) << pl(b)  << endl;
	// cout << pl(res) << endl;

	if (a == b) {
		return res;
	}

	while (pow >= 0) {
		if (jumpNode[a][pow] != jumpNode[b][pow]) {
			res = max({
				res,
				jumpMax[a][pow],
				jumpMax[b][pow]
			});

			a = jumpNode[a][pow];
			b = jumpNode[b][pow];
		}

		pow--;
	}
	assert(jumpNode[a][0] == jumpNode[b][0]);
	return max({res, jumpMax[a][0], jumpMax[b][0]});
}

int getMinimumFuelCapacity(int x, int y) {
	if (n == 2) return -1;

	int res = max(dp[x], get_cost(x, y));
	return res >= inf ? -1 : res;
}

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