Submission #401679

#	Time	Username	Problem	Language	Result	Execution time	Memory
401679		hoaphat1	Swapping Cities (APIO20_swap)	C++17	100 / 100	717 ms	53124 KiB

swap

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

struct graph {
	int n, nlog;
	vector<vector<pair<int,int>>> g;
	vector<vector<int>> pr;
	vector<vector<int>> val;
	vector<int> pos;
	vector<int> end;
	graph() {
		
	}
	void resize(int n) {
		g.resize(n);
		pos.resize(n);
		end.resize(n);
		nlog = 0;
		while (1 << nlog <= n) nlog++;
		pr.resize(n, vector<int> (nlog));
		val.resize(n, vector<int> (nlog));
	}
	void add(int u, int v, int w) {
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	void dfs(int v, int p = 0) {
		static int count = -1;
		pos[v] = ++count;
		pr[v][0] = p;
		for (int i = 1; i < nlog; i++) {
			pr[v][i] = pr[pr[v][i-1]][i-1];
			val[v][i] = max(val[v][i-1], val[pr[v][i-1]][i-1]);
		}
		for (auto&x : g[v]) {
			int u = x.first;
			if (u != p) {
				val[u][0] = x.second;
				dfs(u, v);
			}
		}
		end[v] = count;
	}
	bool anc(int x, int y) {
		return pos[x] <= pos[y] && end[y] <= end[x];
	}
	int lca(int x, int y) {
		if (anc(x, y)) return x;
		if (anc(y, x)) return y;
		for (int i = nlog - 1; i >= 0; i--) {
			if (pr[x][i] && !anc(pr[x][i], y)) x = pr[x][i];
		}
		return pr[x][0];
	}
	int get(int x, int y) {
		int p = lca(x, y);
		int ans = 0;
		for (int i = nlog - 1; i >= 0; i--) {
			if (pr[x][i] && anc(p, pr[x][i])) {
				ans = max(ans, val[x][i]);
				x = pr[x][i];
			}
			if (pr[y][i] && anc(p, pr[y][i])) {
				ans = max(ans, val[y][i]);
				y = pr[y][i];
			}
		}
		return ans;
	}
};

struct dsu {
	vector<int> p;
	int n;
	dsu(int n) {
		resize(n);
	}
	dsu() {
	}
	void resize(int _n) {
		n = _n;
		p = vector<int> (n, -1);
	}
	int get(int x) {
		return p[x] < 0 ? x : p[x] = get(p[x]);
	}
	bool unite(int x, int y) {
		x = get(x); y = get(y);
		if (x != y) {
			if (p[x] < p[y]) swap(x, y);
			p[y] += p[x];
			p[x] = y;
			return true;
		}
		return false;
	}
} d;

const int N = 1e5 + 3;
int n, m;
vector<tuple<int,int,int>> edges;
int deg[N];
int event[N];
vector<int> belong[N];
graph g;

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++) edges.emplace_back(w[i], u[i], v[i]);
	sort(edges.begin(), edges.end());
	d.resize(n);
	g.resize(n);
	for (int i = 0; i < n; i++) belong[i] = {i};
	for (auto&x : edges) {
		deg[get<1>(x)]++;
		deg[get<2>(x)]++;
		int u = d.get(get<1>(x)), v = d.get(get<2>(x));
		bool to = (deg[get<1>(x)] >= 3 || deg[get<2>(x)] >= 3);
		if (u == v) {
			if (!event[u]) {
				for (auto&y : belong[u]) event[y] = get<0> (x);
				belong[u].clear();
			}
		}
		else {
			d.unite(u, v);
			g.add(get<1>(x), get<2>(x), get<0>(x));
			if (!event[u] && !event[v]) {
				if (belong[u].size() < belong[v].size()) swap(u, v);
				for (auto&x : belong[v]) belong[u].push_back(x);
				belong[v].clear();
				if (to) {
					for (auto&y : belong[u]) event[y] = get<0>(x);
					belong[u].clear();
				}
				else {
					if (u != d.get(u)) swap(belong[u], belong[v]);
				}
			}
			else {
				for (auto&y : belong[u]) event[y] = get<0>(x);
				belong[u].clear();
				for (auto&y : belong[v]) event[y] = get<0>(x);
				belong[v].clear();
			}
		}
	}
	g.dfs(0, 0);
}

int getMinimumFuelCapacity(int x, int y) {
	if (!event[x] || !event[y]) return -1;
	return max({event[x], event[y], g.get(x, y)});
}

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