제출 #444598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444598		nonsensenonsense1	자매 도시 (APIO20_swap)	C++17	100 / 100	496 ms	48368 KiB

swap

#include "swap.h"
#include <cstring>
#include <utility>
#include <vector>
#include <algorithm>

const int INF = 0x3f3f3f3f;

void mnm(int &a, int b) 
{
	if (a > b) a = b;
}

void mxm(int &a, int b) 
{
	if (a < b) a = b;
}

struct dsu {
	dsu *p;
	int size;
	bool over;
	std::vector<int> v;
	dsu() {
		over = false;
		p = 0;
		size = 1;
	}
	dsu *find() {
		if (p) return p = p->find();
		return this;
	}
};

const int N = 100000;
const int M = 200000;
const int LG = 17;
int in[N], out[N], f[LG][N], up[LG][N], fi[N], deg[N];
std::vector<std::pair<int, int> > g[N];
std::pair<int, std::pair<int, int> > e[M];
dsu d[N];

void update(std::vector<int> &v, int w) 
{
	while (!v.empty()) {
		fi[v.back()] = w;
		v.pop_back();
	}
}

bool unite(dsu *a, dsu *b, int w) 
{
	a = a->find();
	b = b->find();
	if (a == b) return 0;
	if (a->size < b->size) std::swap(a, b);
	b->p = a;
	a->size += b->size;
	a->v.insert(a->v.end(), b->v.begin(), b->v.end());
	if (a->over || b->over) {
		a->over = true;
		update(a->v, w);
	}
	return 1;
}

void rm(dsu *a, int w) 
{
	a = a->find();
	if (!a->over) {
		a->over = true;
		update(a->v, w);
	}
}

void dfs(int v) 
{
	static int dt = 0;
	in[v] = dt++;
	for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i].first != f[0][v]) {
		f[0][g[v][i].first] = v;
		up[0][g[v][i].first] = g[v][i].second;
		dfs(g[v][i].first);
	}
	out[v] = dt;
}

bool parent(int u, int v) 
{
	return in[u] <= in[v] && out[u] >= out[v];
}

void init(int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> w) 
{
	memset(fi, 0x3f, n << 2);
	for (int i = 0; i < n; ++i) d[i].v.push_back(i);
	for (int i = 0; i < m; ++i) e[i] = std::make_pair(w[i], std::make_pair(u[i], v[i]));
	std::sort(e, e + m);
	for (int i = 0; i < m; ++i) {
		bool way = false;
		if (unite(d + e[i].second.first, d + e[i].second.second, e[i].first)) {
			g[e[i].second.first].push_back(std::make_pair(e[i].second.second, e[i].first));
			g[e[i].second.second].push_back(std::make_pair(e[i].second.first, e[i].first));
		}
		else way = true;
		++deg[e[i].second.first];
		++deg[e[i].second.second];
		if (way || deg[e[i].second.first] == 3 || deg[e[i].second.second] == 3) rm(d + e[i].second.first, e[i].first);
	}
	dfs(0);
	for (int j = 1; j < LG; ++j) for (int i = 0; i < n; ++i) {
		f[j][i] = f[j - 1][f[j - 1][i]];
		up[j][i] = std::max(up[j - 1][i], up[j - 1][f[j - 1][i]]);
	}
}

int getMinimumFuelCapacity(int u, int v) 
{
	int edge = std::min(fi[u], fi[v]);
	for (int t = 0; t < 2; ++t) {
		if (!parent(v, u)) {
			for (int i = LG - 1; i >= 0; --i) if (!parent(f[i][v], u)) {
				edge = std::max(edge, up[i][v]);
				v = f[i][v];
			}
			edge = std::max(edge, up[0][v]);
		}
		std::swap(u, v);
	}
	if (edge == INF) return -1;
	return edge;
}

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