Submission #965950

#	Time	Username	Problem	Language	Result	Execution time	Memory
965950		Gromp15	Swapping Cities (APIO20_swap)	C++17	100 / 100	450 ms	84560 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define db double
#define ll long long
#define ar array
template<typename T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int LOG = 17;
struct dsu {
	vector<vector<int>> adj;
	vector<int> deg, p, sub;
	vector<bool> mark;
	vector<vector<int>> up;
	vector<int> depth, good;
	int who, N;
	dsu() {}
	dsu(int n, int m) : N(n), adj(n + m), deg(n), p(n + m), who(n), sub(n + m), mark(n + m), up(n + m, vector<int>(LOG, -1)), depth(n + m), good(n + m, -1) {
		iota(all(p), 0);
	}
	int get(int v) {
		return v == p[v] ? v : p[v] = get(p[v]);
	}
	void add(int x, int y) {
		int ox = x, oy = y;
		x = get(x), y = get(y);
		p[x] = who, p[y] = who;
		if (deg[ox] == 0) sub[who] += -1;
		else if (deg[ox] == 1) sub[who] += 1;
		if (deg[oy] == 0) sub[who] += -1;
		else if (deg[oy] == 1) sub[who] += 1;
		deg[ox]++, deg[oy]++;
		if (deg[ox] > 2 || deg[oy] > 2) mark[who] = 1;
		adj[who].emplace_back(x);
		if (x != y) adj[who].emplace_back(y);
		who++;
	}
	void process(int sx) {
		auto dfs = [&](auto&& s, int v, int p) -> void {
			for (int u : adj[v]) if (u != p) {
				up[u][0] = v, depth[u] = depth[v] + 1;
				for (int i = 1; i < LOG; i++) {
					if (~up[u][i-1]) up[u][i] = up[up[u][i-1]][i-1];
				}
				s(s, u, v);
				sub[v] += sub[u];
				mark[v] = mark[v] || mark[u];
			}
		};
		dfs(dfs, sx, -1);
		auto dfs2 = [&](auto&& s, int v, int p, int lst) -> void {
			if (v >= N && (mark[v] || sub[v] == 0)) lst = v;
			good[v] = lst;
			for (int u : adj[v]) if (u != p) {
				s(s, u, v, lst);
			}
		};
		dfs2(dfs2, sx, -1, -1);
	}
	int lca(int x, int y) {
		if (depth[x] < depth[y]) swap(x, y);
		int diff = depth[x] - depth[y];
		for (int i = 0; i < LOG; i++) if (diff >> i & 1) x = up[x][i];
		assert(depth[x] == depth[y]);
		for (int i = LOG-1; i >= 0; i--) if (up[x][i] != up[y][i]) x = up[x][i], y = up[y][i];
		return x == y ? x : up[x][0];
	}
};
const int INF = 1e9;
vector<vector<ar<int, 3>>> adj;
vector<int> weights;
int n, m;
dsu d;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N, m = M;
	adj.resize(N + 1);
	d = dsu(n, m);
	for (int i = 0; i < M; i++) {
		adj[U[i]].push_back({V[i], W[i], i});
		adj[V[i]].push_back({U[i], W[i], i});
	}
	vector<int> idx(M);
	iota(all(idx), 0);
	sort(all(idx), [&](int x, int y) { return W[x] < W[y]; });
	for (int i = 0; i < M; i++) {
		d.add(U[idx[i]], V[idx[i]]);
	}
	d.process(n + m - 1);
	weights.resize(m);
	for (int i = 0; i < m; i++) {
		weights[i] = W[idx[i]];
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	int ans = d.good[d.lca(X, Y)];
	return ~ans ? weights[ans - n] : -1;
}

Compilation message (stderr)

swap.cpp: In constructor 'dsu::dsu(int, int)':
swap.cpp:19:11: warning: 'dsu::N' will be initialized after [-Wreorder]
   19 |  int who, N;
      |           ^
swap.cpp:14:22: warning:   'std::vector<std::vector<int> > dsu::adj' [-Wreorder]
   14 |  vector<vector<int>> adj;
      |                      ^~~
swap.cpp:21:2: warning:   when initialized here [-Wreorder]
   21 |  dsu(int n, int m) : N(n), adj(n + m), deg(n), p(n + m), who(n), sub(n + m), mark(n + m), up(n + m, vector<int>(LOG, -1)), depth(n + m), good(n + m, -1) {
      |  ^~~
swap.cpp:19:6: warning: 'dsu::who' will be initialized after [-Wreorder]
   19 |  int who, N;
      |      ^~~
swap.cpp:15:22: warning:   'std::vector<int> dsu::sub' [-Wreorder]
   15 |  vector<int> deg, p, sub;
      |                      ^~~
swap.cpp:21:2: warning:   when initialized here [-Wreorder]
   21 |  dsu(int n, int m) : N(n), adj(n + m), deg(n), p(n + m), who(n), sub(n + m), mark(n + m), up(n + m, vector<int>(LOG, -1)), depth(n + m), good(n + m, -1) {
      |  ^~~

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