Submission #1307813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307813		namhh	Swapping Cities (APIO20_swap)	C++20	100 / 100	237 ms	49304 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 3e5+5;
const int lg = 19;
int n,par[N],h[N],st[N][lg],cur,ck[N],val[N],deg[N];
vector<int>adj[N];
int find(int u){
	if(u == par[u]) return u;
	return par[u] = find(par[u]);
}
void join(int u, int v, int w){
	int x = u;
	int y = v;
	u = find(u);
	v = find(v);
	deg[x]++;
	deg[y]++;
	par[u] = par[v] = par[cur] = cur;
	adj[cur].push_back(u);
	val[cur] = w;
	if(u != v) adj[cur].push_back(v);
	if(u == v || ck[u] || ck[v] || deg[x] >= 3 || deg[y] >= 3) ck[cur] = 1;
	cur++;
}
void dfs(int u, int p){
	st[u][0] = p;
	h[u] = h[p]+1;
	for(int i = 1; i < lg; i++) st[u][i] = st[st[u][i-1]][i-1];
	for(int v: adj[u]) dfs(v,u);
}
int lca(int u, int v){
	if(h[u] < h[v]) swap(u,v);
	for(int i = lg-1; i >= 0; i--){
		if(h[st[u][i]] >= h[v]) u = st[u][i];
	}
	if(u == v) return u;
	for(int i = lg-1; i >= 0; i--){
		if(st[u][i] != st[v][i]){
			u = st[u][i];
			v = st[v][i];
		}
	}
	return st[u][0];
}
struct edges{
	int u,v,w;
};
bool cmp(edges a, edges b){
	return a.w < b.w;
}
vector<edges>loj;
void init(int n, int m, vector<int>u, vector<int>v, vector<int>w){
	for(int i = 0; i < m; i++){
		u[i]++;
		v[i]++;
	    loj.push_back({u[i],v[i],w[i]});
	}
	sort(loj.begin(),loj.end(),cmp);
	for(int i = 1; i <= n; i++) par[i] = i;
	cur = n+1;
	for(auto[u,v,w]: loj) join(u,v,w);
	dfs(n+m,0);
}
int getMinimumFuelCapacity(int u, int v){
	u++;
	v++;
	int dm = lca(u,v);
	if(ck[dm]) return val[dm];
	for(int i = lg-1; i >= 0; i--){
		if(st[dm][i] != 0 && !ck[st[dm][i]]) dm = st[dm][i];
	}
	if(st[dm][0] == 0) return -1;
	else return val[st[dm][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