Submission #297856

#	Time	Username	Problem	Language	Result	Execution time	Memory
297856		tmwilliamlin168	Swapping Cities (APIO20_swap)	C++14	100 / 100	557 ms	41792 KiB

swap

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

#define ar array

const int mxN=1e5;
int n, a[mxN], r[mxN];

struct tree {
	int d[mxN], anc[mxN][17], b1[mxN][17];
	vector<ar<int, 2>> adj[mxN];
	vector<int> adj2[mxN];
	int find(int x) {
		return x^r[x]?r[x]=find(r[x]):x;
	}
	void dfs2(int u, int w) {
		a[u]=min(w, a[u]);
		for(int v : adj2[u])
			dfs2(v, w);
		adj2[u].clear();
	}
	bool join(int x, int y, int w) {
		if((x=find(x))==(y=find(y)))
			return 0;
		r[x]=y;
		if(a[y]<=1e9)
			dfs2(x, w);
		if(a[x]<=1e9)
			dfs2(y, w);
		adj2[y].push_back(x);
		return 1;
	}
	void co(vector<ar<int, 3>> e) {
		iota(r, r+n, 0);
		for(auto f : e) {
			if(join(f[1], f[2], f[0])) {
				adj[f[1]].push_back({f[0], f[2]});
				adj[f[2]].push_back({f[0], f[1]});
				if(adj[f[1]].size()>2||adj[f[2]].size()>2)
					dfs2(find(f[1]), f[0]);
			} else
				dfs2(find(f[1]), f[0]);
		}
	}
	void dfs(int u=0, int p=-1) {
		anc[u][0]=p;
		for(int i=1; i<17; ++i) {
			anc[u][i]=~anc[u][i-1]?anc[anc[u][i-1]][i-1]:-1;
			b1[u][i]=~anc[u][i-1]?max(b1[u][i-1], b1[anc[u][i-1]][i-1]):0;
		}
		for(auto v : adj[u]) {
			if(v[1]^p) {
				b1[v[1]][0]=v[0];
				d[v[1]]=d[u]+1;
				dfs(v[1], u);
			}
		}
	}
	int qry(int x, int y) {
		if(d[x]<d[y])
			swap(x, y);
		int r=0;
		for(int i=16; ~i; --i) {
			if(d[x]-(1<<i)>=d[y]) {
				r=max(b1[x][i], r);
				x=anc[x][i];
			}
		}
		if(x==y)
			return r;
		for(int i=16; ~i; --i) {
			if(anc[x][i]^anc[y][i]) {
				r=max({b1[x][i], b1[y][i], r});
				x=anc[x][i];
				y=anc[y][i];
			}
		}
		return max({b1[x][0], b1[y][0], r});
	}
} t0;

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
	::n=n;
	vector<ar<int, 3>> e;
	for(int i=0; i<m; ++i)
		e.push_back({w[i], u[i], v[i]});
	sort(e.begin(), e.end());
	memset(a, 0x3f, 4*n);
	t0.co(e);
	t0.dfs();
}

int getMinimumFuelCapacity(int x, int y) {
	int b=max(t0.qry(x, y), a[x]);
	return b>1e9?-1:b;
}

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