제출 #1225990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225990		PanosPask	자매 도시 (APIO20_swap)	C++20	36 / 100	205 ms	43888 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;

    int res;
};

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

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

int N, M;

DSU graph;

bool cycle;
int super = 0;

// 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;

vector<int> split;

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

	c.ancestor = b.ancestor;
	c.res = max(a.res, b.res);

	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;
	ancestor[0][node].res = wp;
}

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;
}

void calculate(int node) {
    split[node] = total[node][2];

    for (auto [kid, w] : kids[node]) {
        calculate(kid);
        split[node] = min(split[node], max(split[kid], w));
    }
}

void propagate(int node, int v) {
    split[node] = min(split[node], v);

    for (auto [kid, w] : kids[node]) {
        propagate(kid, max(split[node], w));
    }
}

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

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

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

	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;
	a = merge(a, ancestor[0][a.ancestor]);
	b = merge(b, ancestor[0][b.ancestor]);

    return {l, max(a.res, b.res)};
}

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]);
		}
	}
}

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);
    split.resize(N);
	kids.resize(N);
	graph.init(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());

    super = 0;
	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);
        super = max(super, w);
	}

    cycle = true;
    for (int i = 0; i < N; i++) {
        cycle = (cycle) && (adj_list[i].size() + kids[i].size() == 2);
    }
    if (cycle) {
        return;
    }

	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);
        total[i].pb(INF);
		sort(total[i].begin(), total[i].end());
	}

    dfs(0, 0, INF);
    precalculate();
    calculate(0);
    propagate(0, INF);
}

int getMinimumFuelCapacity(int X, int Y) {
    if (cycle) {
        return super;
    }
    int l, ans;
    tie(l, ans) = lca(X, Y);

    ans = max(ans, split[X]);
    if (ans == INF) {
        return -1;
    }
    else {
        return ans;
    }
}

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