Submission #546037

#	Time	Username	Problem	Language	Result	Execution time	Memory
546037		amunduzbaev	Swapping Cities (APIO20_swap)	C++17	100 / 100	522 ms	49088 KiB

swap

#include "swap.h"
#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array

const int N = 1e5 + 5;
int par[N][20], mx[N][20];
int tin[N], tout[N], t, is[N];
vector<ar<int, 2>> edges[N];

void dfs(int u, int p = -1){
	for(int j=1;j<20;j++){
		par[u][j] = par[par[u][j-1]][j-1];
		mx[u][j] = max(mx[u][j-1], mx[par[u][j-1]][j-1]);
	}
	
	tin[u] = ++t;
	for(auto x : edges[u]){
		if(x[0] == p) continue;
		par[x[0]][0] = u, mx[x[0]][0] = x[1];
		dfs(x[0], u);
	} tout[u] = t;
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
	vector<int> p(m); iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j){
		return (w[i] < w[j]);
	});
	
	vector<int> par(n), sz(n, 1), d(n);
	vector<vector<int>> sub(n);
	for(int i=0;i<n;i++){
		par[i] = i;
		sub[i].push_back(i);
	}
	
	auto upd = [&](int a, int c){
		for(auto x : sub[a]) is[x] = c;
		sub[a].clear();
	};
	function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
	auto merge = [&](int a, int b, int c){
		d[a]++, d[b]++;
		bool t = (d[a] >= 3 || d[b] >= 3);
		a = f(a), b = f(b);
		if(a == b){
			upd(a, c);
			return false;
		}
		
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a, sz[a] += sz[b];
		sub[a].insert(sub[a].end(), sub[b].begin(), sub[b].end());
		
		if(is[a] && is[b]) return true;
		if(!is[a] && !is[b]){
			if(t) upd(a, c);
			return true;
		}
		
		upd(a, c);
		return true;
	};
	
	for(auto i : p){
		if(merge(u[i], v[i], w[i])){
			edges[u[i]].push_back({v[i], w[i]});
			edges[v[i]].push_back({u[i], w[i]});
		}
	}
	
	::par[0][0] = 0;
	dfs(0, -1);
}

bool P(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }
int lca(int a, int b){
	if(P(a, b)) return a;
	if(P(b, a)) return b;
	for(int j=19;~j;j--){
		if(!P(par[a][j], b)) a = par[a][j];
	} return par[a][0];
}

int getMinimumFuelCapacity(int a, int b) {
	int mx = 0;
	int p = lca(a, b);
	//~ cout<<a<<" "<<b<<" "<<p<<"\n";
	{
		int x = a;
		for(int j=19;~j;j--){
			if(!P(par[x][j], p)){
				mx = max(mx, ::mx[x][j]);
				x = par[x][j];
			}
		} if(x != p) mx = max(mx, ::mx[x][0]);
	}
	{
		int x = b;
		for(int j=19;~j;j--){
			if(!P(par[x][j], p)){
				mx = max(mx, ::mx[x][j]);
				x = par[x][j];
			}
		} if(x != p) mx = max(mx, ::mx[x][0]);
	}
	assert(mx);
	if(!is[a]) return -1;
	return max({mx, is[a], is[b]});
}

/*

5 6
0 1 4 
0 2 4
1 2 1
1 3 2
1 4 10 
2 3 3
3
1 2
2 4
0 1

*/

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