Submission #982339

#	Time	Username	Problem	Language	Result	Execution time	Memory
982339		vjudge1	Swapping Cities (APIO20_swap)	C++17	100 / 100	376 ms	75276 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

namespace operators
{
	template <typename T1, typename T2>
	std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
	{
		in >> x.first >> x.second;
		return in;
	}

	template <typename T1, typename T2>
	std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
	{
		out << x.first << " " << x.second;
		return out;
	}

	template <typename T1>
	std::istream &operator>>(std::istream &in, std::vector<T1> &x)
	{
		for (auto &i : x)
			in >> i;
		return in;
	}

	template <typename T1>
	std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
	{
		for (auto &i : x)
			out << i << " ";
		return out;
	}

	template <typename T1>
	std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
	{
		for (auto &i : x)
			out << i << " ";
		return out;
	}
}

// name spaces
using namespace std;
using namespace operators;
// end of name spaces

// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines

const ll INF = (1e18) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;

vector<pair<int, pii>> edges;

struct DSU
{
	vector<int> p;

	void init(int n)
	{
		p.resize(n);
		for (int i = 0; i < n; ++i)
			p[i] = i;
	}

	int getRoot(int a)
	{
		return p[a] == a ? a : p[a] = getRoot(p[a]);
	}

} dsu;
int n, m;
vector<vector<int>> tree, jump;
vector<int> good, cost, tin, tout;
int timer = 0;

void dfs(int v, int pr, int curCost)
{
	tin[v] = ++timer;
	if (good[v])
		curCost = cost[v];
	cost[v] = curCost;

	jump[v][0] = pr;
	for (int i = 1; i < 20; ++i)
		jump[v][i] = jump[jump[v][i - 1]][i - 1];

	for (auto tov : tree[v])
		dfs(tov, v, curCost);
	tout[v] = ++timer;
}

bool isP(int pr, int v)
{
	return tin[pr] <= tin[v] and tout[v] <= tout[pr];
}

int lca(int v, int u)
{
	if (isP(v, u))
		return v;
	if (isP(u, v))
		return u;

	for (int i = 19; i >= 0; --i)
		if (!isP(jump[v][i], u))
			v = jump[v][i];

	return jump[v][0];
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
	tree.resize(N + M);
	jump.resize(N + M, vector<int>(20));
	good.resize(N + M);
	cost.resize(N + M);
	tin.resize(N + M);
	tout.resize(N + M);

	dsu.init(N + M);

	n = N;
	m = M;

	for (int i = 0; i < M; ++i)
		edges.pb({W[i], {U[i], V[i]}});

	sort(all(edges));
	vector<int> deg(N, 0);
	int cnt = 0;
	for (auto [w, e] : edges)
	{
		auto [v, tov] = e;
		deg[v]++;
		deg[tov]++;

		bool isGood = (deg[v] >= 3 or deg[tov] >= 3);
		v = dsu.getRoot(v);
		tov = dsu.getRoot(tov);
		isGood |= (good[v] or good[tov]);

		tree[N + cnt].pb(v);
		dsu.p[v] = dsu.p[tov] = N + cnt;
		if (v != tov)
			tree[N + cnt].pb(tov);
		else
			isGood = true;
		cost[N + cnt] = w;
		good[N + cnt] = isGood;

		cnt++;
	}
	dfs(N + M - 1, N + M - 1, BIG);
}

int getMinimumFuelCapacity(int X, int Y)
{
	int cV = lca(X, Y);
	if (cost[cV] == BIG)
		return -1;
	return cost[cV];
}
// //////////////////////////////
// #include "swap.h"

// #include <cassert>
// #include <cstdio>

// #include <string>
// #include <vector>

// int main()
// {
// 	int N, M;
// 	assert(2 == scanf("%d %d", &N, &M));

// 	std::vector<int> U(M), V(M), W(M);
// 	for (int i = 0; i < M; ++i)
// 	{
// 		assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
// 	}

// 	int Q;
// 	assert(1 == scanf("%d", &Q));

// 	std::vector<int> X(Q), Y(Q);
// 	for (int i = 0; i < Q; ++i)
// 	{
// 		assert(2 == scanf("%d %d", &X[i], &Y[i]));
// 	}

// 	init(N, M, U, V, W);

// 	std::vector<int> minimum_fuel_capacities(Q);
// 	for (int i = 0; i < Q; ++i)
// 	{
// 		minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
// 	}

// 	for (int i = 0; i < Q; ++i)
// 	{
// 		printf("%d\n", minimum_fuel_capacities[i]);
// 	}

// 	return 0;
// }

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