Submission #409865

#	Time	Username	Problem	Language	Result	Execution time	Memory
409865		jhwest2	Swapping Cities (APIO20_swap)	C++14	100 / 100	485 ms	43948 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int M = 1e5 + 10;
const int INF = 1e9 + 10;

int n, m, Deg[M], Cnt[M], Mx[M], Sz[M], Par[M], A[M], Dep[M], P[20][M], B[20][M];
vector<int> V[M];
vector<pint> G[M];
pair<int, pint> E[M << 1];

int Find(int u) {
	return u == Par[u] ? u : Par[u] = Find(Par[u]);
}
bool is_line(int u) {
	int x = Find(u);
	return Mx[x] <= 2 && Cnt[x] == Sz[x] - 1;
}
void Union(int u, int v, int d) {
	if (Find(u) == Find(v)) {
		int x = Find(u);
		Mx[x] = max({ Mx[x], ++Deg[u], ++Deg[v] });
		Cnt[x]++;
		if (!is_line(x)) {
			for (int k : V[x]) A[k] = d; V[x].clear();
		}
		return;
	}
	int x = Find(u), y = Find(v);
	G[x].emplace_back(d, y); G[y].emplace_back(d, x);
	if (V[x].size() < V[y].size()) {
		swap(x, y), swap(u, v);
	}
	Mx[x] = max({ Mx[x], Mx[y], ++Deg[u], ++Deg[v] });
	Cnt[x] += Cnt[y] + 1; Sz[x] += Sz[y];
	for (int k : V[y]) V[x].push_back(k); V[y].clear();
	Par[y] = x;
	if (!is_line(x)) {
		for (int k : V[x]) A[k] = d; V[x].clear();
	}
}
void dfs(int p, int cur) {
	for (auto [d, x] : G[cur]) if (p != x) {
		P[0][x] = cur; Dep[x] = Dep[cur] + 1; B[0][x] = d;
		for (int i = 1; i < 20; i++) {
			P[i][x] = P[i - 1][P[i - 1][x]];
			B[i][x] = max(B[i - 1][x], B[i - 1][P[i - 1][x]]);
		}
		dfs(cur, x);
	}
}
int query(int u, int v) {
	if (Dep[u] < Dep[v]) swap(u, v);
	int ret = 0;
	for (int i = 19; i >= 0; i--) {
		if (Dep[u] - Dep[v] >> i & 1) {
			ret = max(ret, B[i][u]); u = P[i][u];
		}
	}
	for (int i = 19; i >= 0; i--) {
		if (P[i][u] != P[i][v]) {
			ret = max({ ret, B[i][u], B[i][v] });
			u = P[i][u]; v = P[i][v];
		}
	}
	return u == v ? ret : max({ ret, B[0][u], B[0][v] });
}
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++) {
		E[i] = { _W[i], {_U[i], _V[i]} };
	}
	sort(E, E + m);
	for (int i = 0; i < n; i++) {
		V[i].push_back(i); Par[i] = i; Sz[i] = 1; A[i] = INF;
	}
	for (int i = 0; i < m; i++) {
		auto [u, v] = E[i].vb;
		Union(u, v, E[i].va);
	}
	dfs(0, 0);

}

int getMinimumFuelCapacity(int u, int v) {
	int ret = max({ query(u, v), A[u], A[v] });
	return ret == INF ? -1 : ret;
}

Compilation message (stderr)

swap.cpp: In function 'void Union(int, int, int)':
swap.cpp:29:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   29 |    for (int k : V[x]) A[k] = d; V[x].clear();
      |    ^~~
swap.cpp:29:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   29 |    for (int k : V[x]) A[k] = d; V[x].clear();
      |                                 ^
swap.cpp:40:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 |  for (int k : V[y]) V[x].push_back(k); V[y].clear();
      |  ^~~
swap.cpp:40:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |  for (int k : V[y]) V[x].push_back(k); V[y].clear();
      |                                        ^
swap.cpp:43:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   43 |   for (int k : V[x]) A[k] = d; V[x].clear();
      |   ^~~
swap.cpp:43:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |   for (int k : V[x]) A[k] = d; V[x].clear();
      |                                ^
swap.cpp: In function 'void dfs(int, int)':
swap.cpp:47:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |  for (auto [d, x] : G[cur]) if (p != x) {
      |            ^
swap.cpp: In function 'int query(int, int)':
swap.cpp:60:14: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   60 |   if (Dep[u] - Dep[v] >> i & 1) {
      |       ~~~~~~~^~~~~~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:82:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |   auto [u, v] = E[i].vb;
      |        ^

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