Submission #297079

#	Time	Username	Problem	Language	Result	Execution time	Memory
297079		tmwilliamlin168	Swapping Cities (APIO20_swap)	C++14	6 / 100	2076 ms	50980 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], anc2[mxN][17], b1[mxN][17], b2[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;
	}
	bool join(int x, int y) {
		if((x=find(x))==(y=find(y)))
			return 0;
		r[x]=y;
		adj2[y].push_back(x);
		return 1;
	}
	void dfs2(int u, int w) {
		a[u]=min(w, a[u]);
		for(int v : adj2[u])
			dfs2(v, w);
		// adj2[u].clear();
	}
	vector<ar<int, 3>> co(vector<ar<int, 3>> e) {
		iota(r, r+n, 0);
		vector<ar<int, 3>> g;
		for(auto f : e) {
			if(join(f[1], f[2])) {
				adj[f[1]].push_back({f[0], f[2]});
				if(adj[f[1]].size()>2)
					dfs2(find(f[1]), f[0]);
				adj[f[2]].push_back({f[0], f[1]});
				if(adj[f[2]].size()>2)
					dfs2(find(f[2]), f[0]);
			} else
				// g.push_back(f);
				dfs2(find(f[1]), f[0]);
		}
		memset(b2, 0x3f, sizeof(b2));
		return g;
	}
	int gv(int u, int x, int y) {
		int r=a[u];
		for(auto e : adj[u]) {
			if(e[1]^x&&e[1]^y) {
				r=min(e[0], r);
				break;
			}
		}
		return r;
	}
	void dfs(int u=0, int p=-1) {
		anc[u][0]=p;
		anc2[u][0]=u;
		for(int i=1; i<17; ++i) {
			anc[u][i]=~anc[u][i-1]?anc[anc[u][i-1]][i-1]:-1;
			anc2[u][i]=~anc[u][i-1]?anc2[anc[u][i-1]][i-1]:0;
			b1[u][i]=~anc[u][i-1]?max(b1[u][i-1], b1[anc[u][i-1]][i-1]):0;
		}
		if(u) {
			b2[u][1]=gv(p, u, anc[p][0]);
			for(int i=2; i<17; ++i)
				b2[u][2]=~anc[u][i-1]?min({b2[u][i-1], b2[anc[u][i-1]][i-1], gv(anc[u][i-1], anc2[u][i-1], anc[anc[u][i-1]][0])}):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});
	}
	int qry2(int x, int y) {
		if(d[x]<d[y])
			swap(x, y);
		int r=2e9, x2=x, y2=y;
		for(int i=16; ~i; --i) {
			if(d[x]-(1<<i)>=d[y]) {
				if(x2^x)
					r=min(gv(x, x2, anc[x][0]), r);
				r=min(b2[x][i], r);
				x2=anc2[x][i];
				x=anc[x][i];
			}
		}
		if(x==y)
			return r;
		for(int i=16; ~i; --i) {
			if(anc[x][i]^anc[y][i]) {
				if(x2^x)
					r=min(gv(x, x2, anc[x][0]), r);
				if(y2^y)
					r=min(gv(y, y2, anc[y][0]), r);
				r=min({b2[x][i], b2[y][i], r});
				x2=anc2[x][i];
				y2=anc2[y][i];
				x=anc[x][i];
				y=anc[y][i];
			}
		}
		if(x2^x)
			r=min(gv(x, x2, anc[x][0]), r);
		if(y2^y)
			r=min(gv(y, y2, anc[y][0]), r);
		return min(gv(anc[x][0], x, y), r);
	}
} t0;//, t1;

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);
	e=t0.co(e);
	/*t1.co(e);
	for(auto f : e) {
		a[f[1]]=max(f[0], a[f[1]]);
		a[f[2]]=max(f[0], a[f[2]]);
	}*/
	t0.dfs();
	//t1.dfs();
}

int getMinimumFuelCapacity(int x, int y) {
	// cout << t0.qry(x, y) << " " << t0.qry2(x, y) << " " << t1.qry(x, y) << endl;
	// int a=min(max(t0.qry(x, y), t0.qry2(x, y)), t1.qry(x, y));
	int b=max(t0.qry(x, y), a[x]);
	return b>1e9?-1:b;
}

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