Submission #571060

#	Time	Username	Problem	Language	Result	Execution time	Memory
571060		grt	Swapping Cities (APIO20_swap)	C++17	100 / 100	439 ms	60924 KiB

swap

//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int INF = 1e9, nax = 100 * 1000 + 10;
vector<tuple<int, int, int>> edges;
int p[nax * 3], ed[nax * 3], leaves[nax * 3], sz[nax * 3];
int cost[nax * 3];
bool good[3 * nax];
int deg[nax], nxt;

int Fund(int x) {
	if(p[x] != x) {
		p[x] = Fund(p[x]);
	}
	return p[x];
}

vi G[3 * nax];

void Onion(int a, int b, int w) {
	int pa = Fund(a), pb = Fund(b);
	if(pa == pb) {
		p[pa] = nxt;
		p[nxt] = nxt;
		G[nxt].PB(pa);
		leaves[nxt] = leaves[pa], good[nxt] = good[pa], ed[nxt] = ed[pa];
		sz[nxt] = sz[pa];
	} else {
		p[pa] = nxt, p[pb] = nxt;
		p[nxt] = nxt;
		G[nxt].PB(pa);
		G[nxt].PB(pb);
		leaves[nxt] = leaves[pa] + leaves[pb];
		good[nxt] = good[pa] | good[pb];
		ed[nxt] = ed[pa] + ed[pb];
		sz[nxt] = sz[pa] + sz[pb];
	}
	if(deg[a] == 1) leaves[nxt]--;
	else if(deg[a] == 0) leaves[nxt]++;
	if(deg[b] == 1) leaves[nxt]--;
	else if(deg[b] == 0) leaves[nxt]++;
	deg[a]++, deg[b]++;
	ed[nxt]++;
	if(ed[nxt] >= sz[nxt]) {
		good[nxt] = 1;
	} else if(leaves[nxt] > 2) {
		good[nxt] = 1;
	}
	cost[nxt] = w;
	nxt++;
}

int par[3 * nax][19];
int dep[3 * nax];

void dfs(int x, int pr) {
	par[x][0] = pr;
	//cerr << x << ": " << good[x] << "\n";
	for(int y : G[x]) {
		//cerr << x << " -> " << y << "\n";
		dep[y] = dep[x] + 1;
		dfs(y, x);
	}
}

void init(int n, int m, vi U, vi V, vi W) {
	for(int i = 0; i < n; ++i) {
		p[i] = i;
		sz[i] = 1;
		leaves[i] = 0;
		ed[i] = deg[i] = 0;
	}
	for(int i = 0; i < m; ++i) {
		edges.emplace_back(W[i], U[i], V[i]);
	}
	sort(edges.begin(), edges.end());
	nxt = n;
	for(auto [w, u, v] : edges) {
		Onion(u, v, w);
	}
	nxt--;
	dfs(nxt, 0);
	par[nxt][0] = nxt;
	for(int step = 1; step < 19; ++step) {
		for(int i = 0; i <= nxt; ++i) {
			par[i][step] = par[par[i][step - 1]][step - 1];
		}
	}
}

int lca(int x, int y) {
	if(dep[x] > dep[y]) swap(x, y);
	for(int i = 18; i >= 0; --i) {
		if(dep[par[y][i]] >= dep[x]) {
			y = par[y][i];
		}
	}
	if(x == y) return x;
	for(int i = 18; i >= 0; --i) {
		if(par[x][i] != par[y][i]) {
			x = par[x][i];
			y = par[y][i];
		}
	}
	return par[x][0];
}

int getMinimumFuelCapacity(int x, int y) {
	int z = lca(x, y);
	//cerr << "Z: " << z << "\n";
	if(good[z]) return cost[z];
	for(int i = 18; i >= 0; --i) {
		if(!good[par[z][i]]) {
			z = par[z][i];
		}
	}
	z = par[z][0];
	if(!good[z]) {
		return -1;
	} else {
		return cost[z];
	}
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
	//cout << getMinimumFuelCapacity(1, 2) << "\n";
	//cout << getMinimumFuelCapacity(2, 4) << "\n";
	//cout << getMinimumFuelCapacity(0, 1) << "\n";
//}

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