Submission #726749

#	Time	Username	Problem	Language	Result	Execution time	Memory
726749		SanguineChameleon	Swapping Cities (APIO20_swap)	C++17	100 / 100	214 ms	26752 KiB

swap

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

const int maxN = 1e5 + 20;
const int inf = 1e9 + 20;
bool flag[maxN];
vector<pair<int, int>> adj[maxN];
int deg[maxN];
int depth[maxN];
pair<int, int> par[maxN];
int T[maxN];
vector<pair<int, int>> tree;
int ROOT;
bool sub1, sub2;
int N, M, lim;
bool f1, f2;

int root(int u) {
	if (par[u].first == -1) {
		return u;
	}
	return root(par[u].first);
}

void update(int u, int v, int w) {
	deg[u]++;
	deg[v]++;
	sub2 &= (deg[u] <= 2);
	sub2 &= (deg[v] <= 2);
	int ru = root(u);
	int rv = root(v);
	if (ru == rv) {
		T[ru] = min(T[ru], w);
		return;
	}
	if (depth[ru] > depth[rv]) {
		swap(ru, rv);
	}
	T[rv] = min(T[rv], max(T[ru], w));
	if (deg[u] >= 3 || deg[v] >= 3) {
		T[rv] = min(T[rv], w);
	}
	par[ru] = {rv, w};
	tree.push_back({ru, rv});
	if (depth[ru] == depth[rv]) {
		depth[rv]++;
	}
}

void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
	N = _N;
	M = _M;
	sub1 = (M == (N - 1));
	sub2 = true;
	vector<pair<int, pair<int, int>>> edges(M);
	for (int i = 0; i < M; i++) {
		adj[U[i]].push_back({V[i], W[i]});
		adj[V[i]].push_back({U[i], W[i]});
		edges[i] = make_pair(W[i], make_pair(U[i], V[i]));
	}
	for (int i = 0; i < N; i++) {
		T[i] = inf;
		par[i] = {-1, -1};
	}
	sort(edges.begin(), edges.end());
	for (auto e: edges) {
		int w = e.first;
		int u = e.second.first;
		int v = e.second.second;
		update(u, v, w);
	}
	for (int i = 0; i < N; i++) {
		depth[i] = -1;
	}
	ROOT = root(0);
	depth[ROOT] = 1;
	reverse(tree.begin(), tree.end());
	for (auto e: tree) {
		int u = e.first;
		int v = e.second;
		assert(depth[v] != -1);
		depth[u] = depth[v] + 1;
	}
	for (int i = 0; i < N; i++) {
		assert(depth[i] != -1);
		if (i != ROOT) {
			assert(par[i].first != -1);
		}
	}
}

void dfs(int u) {
	flag[u] = true;
	int cnt = 0;
	for (auto e: adj[u]) {
		int v = e.first;
		int w = e.second;
		if (w <= lim) {
			cnt++;
		}
		if (w <= lim && !flag[v]) {
			dfs(v);
		}
	}
	f1 &= (cnt <= 2);
	f2 |= (cnt <= 1);
}

int getMinimumFuelCapacity(int u, int v) {
	int tmp_u = u;
	int tmp_v = v;
	int res1 = 0;
	int res2 = inf;
	if (depth[u] < depth[v]) {
		swap(u, v);
	}
	while (depth[u] != depth[v]) {
		res1 = max(res1, par[u].second);
		u = par[u].first;
		assert(u != -1);
	}
	while (u != v) {
		res1 = max(res1, par[u].second);
		u = par[u].first;
		res1 = max(res1, par[v].second);
		v = par[v].first;
		assert(u != -1);
		assert(v != -1);
	}
	u = tmp_u;
	int cur = 0;
	int res7 = inf;
	while (u != -1) {
		res7 = min(res7, max(T[u], cur));
		cur = max(cur, par[u].second);
		u = par[u].first;
	}
	v = tmp_v;
	cur = 0;
	int res8 = inf;
	while (v != -1) {
		res8 = min(res8, max(T[v], cur));
		cur = max(cur, par[v].second);
		v = par[v].first;
	}
	int res = max(res1, min(res7, res8));
	if (res == inf) {
		return -1;
	}
	else {
		return res;
	}
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:114:6: warning: unused variable 'res2' [-Wunused-variable]
  114 |  int res2 = inf;
      |      ^~~~

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