Submission #576401

#	Time	Username	Problem	Language	Result	Execution time	Memory
576401		Arnch	Swapping Cities (APIO20_swap)	C++17	100 / 100	391 ms	65620 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, inf = 2e9, Log = 25;

int n, m, up[N], vp[N], wp[N], h[N], ans[N], par[N][Log], p[N], tim;
vector<int> sor;
vector<int> child[N];
struct node {
	int par, sz, s, e, ans;
	bool isp;
	node() {
		par = sz = isp = s = e = 0;
		ans = inf;
	}
} x[N << 2];

bool cmp(int i, int j) {
	return wp[i] < wp[j];
}

int find(int u) {
	if(p[u] == u) return u;
	return p[u] = find(p[u]);
}
void merge(int u, int v, int t) {
	int X = find(u), Y = find(v);
	if(X == Y) {
		if(x[X].ans == inf) {
			x[X].ans = t;
			x[X].isp = 0; 
		}
		return;
	}
	child[tim].push_back(X), child[tim].push_back(Y);
	x[tim].sz = x[X].sz + x[Y].sz;
	x[X].par = tim, x[Y].par = tim, p[X] = tim, p[Y] = tim;
	if(x[X].isp == 0 || x[Y].isp == 0) {
		x[tim].isp = 0;
		x[tim].ans = t;
	}
	else {
		if((u == x[X].s || u == x[X].e) && (v == x[Y].s || v == x[Y].e)) {
			x[tim].isp = 1;
			x[tim].ans = inf;
			x[tim].s = (u == x[X].s) ? (x[X].e) : (x[X].s);
			x[tim].e = (v == x[Y].s) ? (x[Y].e) : (x[Y].s);
		}
		else {
			x[tim].isp = 0;
			x[tim].ans = t;
		}
	}
	tim++;
}

void dfs(int u, int p) {
	ans[u] = min(ans[u], x[u].ans);
	par[u][0] = p;
	for(int i = 1; i < Log; i++) par[u][i] = par[par[u][i - 1]][i - 1];
	for(auto i : child[u]) {
		h[i] = h[u] + 1;
		ans[i] = ans[u];
		dfs(i, u);
	}
}

int get_par(int u, int y) {
	for(int i = 0; i < Log; i++) {
		if((y >> i) & 1) u = par[u][i];	
	}
	return u;
}

int lca(int u, int v) {
	if(h[u] > h[v]) swap(u, v);
	v = get_par(v, h[v] - h[u]);
	if(u == v) return u;
	for(int i = Log - 1; i >= 0; i--) {
		if(par[u][i] != par[v][i]) {
			u = par[u][i], v = par[v][i];
		}
	}
	return par[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n = N, m = M;
	for(int i = 0; i < m; i++) {
		up[i] = U[i], vp[i] = V[i], wp[i] = W[i];
		sor.push_back(i);
	}
	sort(sor.begin(), sor.end(), cmp);
	tim = n;
	for(int i = 0; i < 2 * n; i++) {
		p[i] = i;
		x[i].par = i, x[i].sz = 1, x[i].e = i, x[i].s = i, x[i].isp = 1;
	}
	for(auto i : sor) {
		merge(up[i], vp[i], wp[i]);
	}
	for(int i = 0; i < 2 * N; i++) ans[i] = inf;
	dfs(tim - 1, tim - 1);
}

int getMinimumFuelCapacity(int X, int Y) {
	int lc = lca(X, Y);
	if(ans[lc] >= inf) return -1;
	return ans[lc];
}

Compilation message (stderr)

swap.cpp: In constructor 'node::node()':
swap.cpp:15:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   15 |   par = sz = isp = s = e = 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