Submission #788048

#	Time	Username	Problem	Language	Result	Execution time	Memory
788048		ToniB	Swapping Cities (APIO20_swap)	C++17	6 / 100	113 ms	19176 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 2;
const int LOG = 18;

int n, m, cycle[MAXN], uf[MAXN], sz[MAXN], cnt[MAXN];
int dep[MAXN], bl[MAXN][LOG], bl_w[MAXN][LOG];
bool uf_bio[MAXN];
vector<pair<int, int> > adj[MAXN], tree[MAXN];
vector<pair<int, pii> > edges;

int f(int x){
	while(uf[x] != -1) x = uf[x];
	return x;
}
void join(int u, int v, int edge){
	if(uf_bio[u] ^ uf_bio[v]){
		if(uf_bio[v]) swap(u, v);
		cycle[v] = edge;
		uf_bio[v] = 1;
	}
	if(sz[u] > sz[v]) swap(u, v);
	sz[v] += sz[u];
	uf[u] = v;
}

int calc(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	int ret = 0, lift = u;
	for(int i = 0; i < LOG; ++i){
		if(dep[u] - dep[v] & 1 << i){
			ret = max(ret, bl_w[lift][i]);
			lift = bl[lift][i];
		}
	}
	u = lift;

	if(u == v) return ret;

	for(int i = LOG - 1; i >= 0; --i){
		if(bl[u][i] != bl[v][i]){
			ret = max(ret, bl_w[u][i]);
			ret = max(ret, bl_w[v][i]);
			u = bl[u][i];
			v = bl[v][i];
		}
	}
	ret = max(ret, bl_w[u][0]);
	ret = max(ret, bl_w[v][0]);
	return ret;
}

void dfs(int node, int anc, int edge = 0){
	bl[node][0] = anc;
	bl_w[node][0] = edge;
	dep[node] = dep[anc] + 1;
	for(pii x : tree[node]){
		if(x.X == anc) continue;
		dfs(x.X, node, x.Y);
	}
}

void connect(int node, int edge){
	if(!uf_bio[node]){
		uf_bio[node] = 1;
		cycle[node] = edge;
	}
}

void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w){
	n = _n; m = _m;
	for(int i = 0; i < n; ++i){
		uf[i] = -1; sz[i] = 1;
	}
	
	for(int i = 0; i < m; ++i){
		adj[u[i]].push_back({v[i], w[i]});
		adj[v[i]].push_back({u[i], w[i]});
		edges.push_back({w[i], {u[i], v[i]}});
	}

	sort(edges.begin(), edges.end());

	for(auto p : edges){
		int u = p.Y.X, v = p.Y.Y;
		++cnt[u]; ++cnt[v];
		int fu = f(u), fv = f(v);
		if(cnt[u] >= 3) connect(fu, p.X);
		if(cnt[v] >= 3) connect(fv, p.X);
		u = fu; v = fv;
		if(u == v){
			connect(u, p.X);
		} else {
			join(u, v, p.X);
			tree[p.Y.X].push_back({p.Y.Y, p.X});
			tree[p.Y.Y].push_back({p.Y.X, p.X});
		}
	}
//	
//	for(int i = 0; i < n; ++i){
//		int node = i;
//		while(node != -1 && !uf_bio[node]){
//			node = uf[node];
//		}
//		if(node != -1) cycle[i] = cycle[node];
//	}
//	
//	dfs(0, 0);
//
//	for(int j = 1; j < n; ++j){
//		for(int i = 0; i < n; ++i){
//			bl[i][j] = bl[bl[i][j - 1]][j - 1];
//			bl_w[i][j] = max(bl_w[i][j - 1], bl_w[bl[i][j - 1]][j - 1]);
//		}
//	}
}
int getMinimumFuelCapacity(int x, int y){
	if(m + 1 == n) return -1;
	return edges[m - 1].X;
	if(min(cycle[x], cycle[y]) == 0) return -1;
	int val = calc(x, y);
	return max(val, min(cycle[x], cycle[y]));
}

Compilation message (stderr)

swap.cpp: In function 'int calc(int, int)':
swap.cpp:35:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   35 |   if(dep[u] - dep[v] & 1 << i){
      |      ~~~~~~~^~~~~~~~

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