Submission #1130405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130405		ByeWorld	Swapping Cities (APIO20_swap)	C++20	100 / 100	406 ms	88572 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 3e5+15;
const int INF = 1e9+10;
const int LOG = 20;
const int MOD = 1e9+7;
void chmx(int &a,int b){ a = max(a, b); }
void chmn(int &a, int b){ a = min(a, b); }

int n, m;
vector <ipii> edge;
int cnt, anc[MAXN][LOG+5], val[MAXN][LOG+5];
vector <int> adj[MAXN];
int dep[MAXN];

void dfs(int nw, int par){
	dep[nw] = dep[par]+1;
	for(auto nx : adj[nw]) 
		dfs(nx, nw);
}
struct dsu {
	int par[MAXN], le[MAXN], ri[MAXN];
	bool tag[MAXN];
	void bd(){
		tag[0] = 1;
		for(int i=1; i<=n+m; i++){
			par[i] = le[i] = ri[i] = i;
		}
	}
	int f(int x){
		return (par[x]==x ? x : par[x]=f(par[x]));
	}
	bool con(int x, int y){
		return f(x) == f(y);
	}
	void mer(int x, int y){
		x = f(x); y = f(y);
		if(x==y) return;
		par[y] = x;
	}
	void gab(int a, int x, int y){
		int b = f(x), c = f(y);
		tag[a] = (tag[b] | tag[c]);

		int p = -1;
		if(x==le[b] || y==le[b]) p = ri[b];
		if(x==ri[b] || y==ri[b]) p = le[b];

		int q = -1;
		if(x==le[c] || y==le[c]) q = ri[c];
		if(x==ri[c] || y==ri[c]) q = le[c];
		
		le[a] = p; ri[a] = q;
		if(p==-1 || q==-1) tag[a] = 1;
		mer(a, x); mer(a, y);
	}
} DSU;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N; m = M;
	for(int i=0; i<m; i++)
		edge.pb({W[i], {U[i]+1, V[i]+1}});	
	for(int j=0; j<LOG; j++)
		for(int i=0; i<=n+m; i++)
			val[i][j] = INF;

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

	DSU.bd();
	cnt = n;
	for(auto [wei, p] : edge){
		int x = p.fi, y = p.se;
		cnt++; 
		if(DSU.con(x, y)){
			val[DSU.f(x)][0] = wei; 
			anc[DSU.f(x)][0] = cnt;

			adj[cnt].pb(DSU.f(x));
			DSU.mer(cnt, x);
			DSU.tag[cnt] = 1;
		} else {
			val[DSU.f(x)][0] = wei;
			val[DSU.f(y)][0] = wei;

			anc[DSU.f(x)][0] = cnt;
			anc[DSU.f(y)][0] = cnt;

			adj[cnt].pb(DSU.f(x)); adj[cnt].pb(DSU.f(y));
			DSU.gab(cnt, x, y);
		}
// cout << x <<' ' << y << " pq\n";
// 	for(int p=1; p<=7; p++){
// 		cout << p << ' ' << DSU.f(p) << ' ' << DSU.le[p]<<' '<<DSU.ri[p]<< " p\n";
// 	}
	}
	dfs(n+m, 0);

	for(int j=1; j<LOG; j++){
		for(int i=1; i<=n+m; i++){
			anc[i][j] = anc[anc[i][j-1]][j-1];
			val[i][j] = max(val[i][j-1], val[anc[i][j-1]][j-1]);
		}
	}
}

int getMinimumFuelCapacity(int X, int Y) {
	X++; Y++;
	int mx = 0;
	// cout << dep[X]<< ' ' << dep[Y] << " dep\n";
	if(dep[X] < dep[Y]) swap(X, Y);
	for(int i=LOG-1; i>=0; i--){
		if(dep[anc[X][i]] >= dep[Y]){
			chmx(mx, val[X][i]);
			X = anc[X][i]; 
		}
	}
	if(X != Y){
		for(int i=LOG-1; i>=0; i--){
			if(anc[X][i] != anc[Y][i]){
				chmx(mx, max(val[X][i], val[Y][i]));
				X = anc[X][i]; Y = anc[Y][i];
			}
		}
		// cout << X << ' '<< Y << "awal\n";
		chmx(mx, val[X][0]); X = anc[X][0];
		// cout<< X << " x\n";
	}
	if(DSU.tag[X]) return mx;

	int mn = INF;
	for(int i=LOG-1; i>=0; i--){
		if(DSU.tag[anc[X][i]]) chmn(mn, max(mx,val[X][i]) );
		else {
			chmx(mx, val[X][i]);
			X = anc[X][i];
		}
	}
	if(DSU.tag[anc[X][0]]) chmn(mn, max(mx,val[X][0]) );
	return (mn>=INF ? -1 : mn);
}

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