Submission #1225904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225904		PanosPask	자매 도시 (APIO20_swap)	C++20	7 / 100	214 ms	51256 KiB

swap

#include "swap.h"

#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>
#include <iostream>

#define mp make_pair
#define pb push_back
#define CHECK_BIT(var, pos) (var & (1 << (pos)))

using namespace std;

typedef pair<int, int> pi;

const int INF = 1e9 + 2;
const int MAXUP = 19;

struct DSU {
	int size;
	vector<int> rep;
	vector<int> rank;

	void init(int N) {
		size = N;
		rank.assign(size, 0);
		rep.resize(size);

		for (int i = 0; i < N; i++) {
			rep[i] = i;
		}
	}

	int find(int a) {
		if (a == rep[a]) {
			return a;
		}
		rep[a] = find(rep[a]);
		return rep[a];
	}

	bool unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) {
			return false;
		}

		if (rank[a] < rank[b]) {
			swap(a, b);
		}
		if (rank[a] == rank[b]) {
			rank[a]++;
		}

		rep[b] = a;
		return true;
	}
};

struct State {
	// We have convered the range [node, ancestor]
	int ancestor;

	// Best edge in the range, ignoring:
	// a) Edges from kids to parents in the range
	// b) All edges of bottom node
	int best;

	// Maximum edge in the path from node to parent
	int mx;
};

struct Edge {
	int u, v, w;
};

bool operator < (Edge a, Edge b) {
	return a.w < b.w;
}

int N, M;

DSU graph;

// Total edge weights of any single node
vector<vector<int>> total;

// Referring to the graph OUTSIDE MST
vector<vector<pi>> adj_list;

// Referring to the MST
vector<pi> par;
vector<vector<pi>> kids;
vector<int> dep;
vector<vector<State>> ancestor;
vector<Edge> edges;

// Best path from node to par using edge outside the MST
vector<int> nicepath;

State merge(State a, State b) {
	State c;

	c.ancestor = b.ancestor;
	c.best = min(a.best, b.best);
	c.mx = max(a.mx, b.mx);

	return c;
}

void dfs(int node, int p, int wp) {
	par[node] = mp(p, wp);
	if (node) {
		kids[node].erase(find(kids[node].begin(), kids[node].end(), mp(p, wp)));
	}
	for (auto [kid, w] : kids[node]) {
		dep[kid] = dep[node] + 1;
		dfs(kid, node, w);
	}

	tie(p, wp) = par[node];

	ancestor[0][node].ancestor = p;
	if (wp != total[p][0] && par[p].second != total[p][0]) {
		ancestor[0][node].best = total[p][0];
	}
	else if (wp != total[p][1] && par[p].second != total[p][1]) {
		ancestor[0][node].best = total[p][1];
	}
	else {
		ancestor[0][node].best = total[p][2];
	}
	ancestor[0][node].mx = wp;
}

void precalculate(void) {
	for (int up = 1; up < MAXUP; up++) {
		for (int i = 0; i < N; i++) {
			ancestor[up][i] = merge(ancestor[up - 1][i], ancestor[up - 1][ancestor[up - 1][i].ancestor]);
		}
	}
}

State jump(State a, int b) {
	for (int up = MAXUP - 1; up >= 0; up--) {
		if (CHECK_BIT(b, up)) {
			a = merge(a, ancestor[up][a.ancestor]);
		}
	}

	return a;
}

// Best outside edge in the path a--b and maximum edge in the path a--b
tuple<int, int, int> lca(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}

	State a = {u, INF, 0};
	State b = {v , INF, 0};

	a = jump(a, dep[u] - dep[v]);
	if (a.ancestor == b.ancestor) {
		return {a.ancestor, a.best, a.mx};
	}

	for (int up = MAXUP - 1; up >= 0; up--) {
		State n_a = merge(a, ancestor[up][a.ancestor]);
		State n_b = merge(b, ancestor[up][b.ancestor]);

		if (n_a.ancestor != n_b.ancestor) {
			a = n_a;
			b = n_b;
		}
	}

	int l = ancestor[0][a.ancestor].ancestor;
	int best = min(a.best, b.best);

	int e1 = par[a.ancestor].second;
	int e2 = par[b.ancestor].second;
	if (e1 > e2) {
		swap(e1, e2);
	}
	if (total[l][0] == e1) {
		if (total[l][1] == e2) {
			best = min(best, total[l][2]);
		}
		else {
			best = min(best, total[l][1]);
		}
	}
	else {
		best = min(best, total[l][0]);
	}

	a = merge(a, ancestor[0][a.ancestor]);
	b = merge(b, ancestor[0][b.ancestor]);
	return {l, best, max(a.mx, b.mx)};
}

int findpath(int i) {
	int ans = INF;

	for (auto [v, w] : adj_list[i]) {
		int l, out, in;
		tie(l, out, in) = lca(i, v);

		ans = min(ans, max(in, w));
	}
	return ans;
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
	N = n;
	M = m;

	adj_list.resize(N);
	par.resize(N);
	kids.resize(N);
	graph.init(N);
	nicepath.resize(N);
	dep.assign(N, 0);
	ancestor.resize(MAXUP, vector<State>(N));
	total.resize(N);
	for (int i = 0; i < M; i++) {
		edges.pb({U[i], V[i], W[i]});
	}
	sort(edges.begin(), edges.end());

	for (auto [u, v, w] : edges) {
		if (graph.unite(u, v)) {
			kids[u].pb(mp(v, w));
			kids[v].pb(mp(u, w));
		}
		else {
			adj_list[u].pb(mp(v, w));
			adj_list[v].pb(mp(u, w));
		}

		total[u].pb(w);
		total[v].pb(w);
	}

	for (int i = 0; i < N; i++) {
		// Push back "infinite" weight edge (if at any point we use any of these, ans is -1)
		total[i].pb(INF);
		sort(total[i].begin(), total[i].end());
	}

	
	par[0] = mp(0, 0);
	dep[0] = 0;
	dfs(0, 0, INF);
	precalculate();

	for (int i = 0; i < N; i++) {
		nicepath[i] = findpath(i);
	}
}

int wait(int X, int e) {
	int e1 = total[X][0];
	int e2 = total[X][1];

	if (e1 == e) {
		e1 = total[X][2];
	}
	else if (e2 == e) {
		e2 = total[X][2];
	}

	return max(e1, e2);
}

int getMinimumFuelCapacity(int X, int Y) {
	int l, out, in;
	tie(l, out, in) = lca(X, Y);

	int ans = in;

	// Find alternatives;
	int alt = min(nicepath[Y], wait(Y, par[Y].second));

	if (Y == l) {
		swap(X, Y);
	}
	
	if (X != l) {
		alt = min(alt, out);
		alt = min(alt, min(nicepath[X], wait(X, par[X].second)));
	}
	else {
		State s = {Y, INF, 0};
		s = jump(s, dep[Y] - dep[X] - 1);
		l = s.ancestor;
		out = s.best;
		in = s.mx;

		int e = par[l].second;
		alt = min(alt, out);
		alt = min(alt, min(nicepath[X], wait(X, e)));	
	}

	ans = max(ans, alt);
	if (ans == INF) {
		return -1;
	}
	else {
		return ans;
	}
}

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