Submission #676529

#	Time	Username	Problem	Language	Result	Execution time	Memory
676529		NothingXD	Swapping Cities (APIO20_swap)	C++14	100 / 100	312 ms	57600 KiB

swap

#include "swap.h"

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e5 + 10;
const int lg = 20;

int n, m, a[maxn], dsu[maxn], d[maxn], leaf[maxn], par[maxn][lg], h[maxn], vercnt;
bool cycle[maxn], ok[maxn];
vector<int> g[maxn];

int getdsu(int v){
	return (dsu[v] == -1? v: dsu[v] = getdsu(dsu[v]));
}

void merge(int u, int v, int w){
	int U = getdsu(u), V = getdsu(v);
	if (U == V){
		vercnt++;
		cycle[vercnt] = true;
		dsu[U] = vercnt;
		g[vercnt].push_back(U);
		leaf[vercnt] = leaf[U];
	}
	else{
		vercnt++;
		dsu[U] = dsu[V] = vercnt;
		g[vercnt].push_back(U);
		g[vercnt].push_back(V);
		leaf[vercnt] = leaf[U] + leaf[V];
		cycle[vercnt] = (cycle[U] || cycle[V]);
	}
	if (d[u] == 1) leaf[vercnt]--;
	if (d[v] == 1) leaf[vercnt]--;
	d[u]++;
	d[v]++;
	ok[vercnt] = (cycle[vercnt] || (leaf[vercnt] > 2));
	a[vercnt] = w;
}

void dfs(int v, int p = -1){
	if (!ok[v]){
		if (p == -1) a[v] = -1;
		else a[v] = a[p];
	}
	par[v][0] = p;
	for (int i = 1; i < lg; i++){
		if (par[v][i-1] != -1) par[v][i] = par[par[v][i-1]][i-1];
	}
	for (auto u: g[v]){
		h[u] = h[v] + 1;
		dfs(u, v);
	}
}

int getpar(int v, int x){
	for (int i = 0; i < lg; i++) if ((x >> i) & 1) v = par[v][i];
	return v;
}

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

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	memset(dsu, -1, sizeof dsu);
	memset(par, -1, sizeof par);
	n = N, m = M;
	for (int i = 1; i <= n; i++) leaf[i] = 1;
	vector<pair<int,pii>> edge;
	for (int i = 0; i < m; i++) edge.push_back({W[i], {U[i]+1, V[i]+1}});
	sort(all(edge));
	vercnt = n;
	for (auto [w, x]: edge){
		merge(x.F, x.S, w);
	}
	dfs(vercnt);
}

int getMinimumFuelCapacity(int X, int Y) {
	int v = lca(X+1, Y+1);
	return a[v];
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:118:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |  for (auto [w, x]: 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