Submission #299803

#	Time	Username	Problem	Language	Result	Execution time	Memory
299803		jacobtpl	Swapping Cities (APIO20_swap)	C++14	0 / 100	2063 ms	23764 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 1100000000
#define sz(x) (int)(x).size()
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define ii pair<int,int>

int n,m;
vector<pair<int,ii> > e,ne;
struct ufds {
	vector<int> p;
	ufds(int n) {
		p.assign(n,0);
		for (int i=0;i<n;i++) p[i]=i;
	}
	int find(int x) {
		return (p[x]==x)?x:(p[x]=find(p[x]));
	}
	void join(int x,int y) {
		int a=find(x),b=find(y);
		if (a!=b) p[a]=b;
	}
	bool same(int x,int y) {
		return (find(x)==find(y));
	}
};

vector<ii> adj[100005],fadj[100005];
int p[100005],pre[100005],bd[100005],dp[100005],cur;
void form(int v,int d) {
	pre[v]=cur++;
	dp[v]=d;
	for (ii x:adj[v]) {
		if (x.first==p[v]) continue;
		p[x.first]=v;
		form(x.first,d+1);
	}
	bd[v]=cur-1;
}
void add_edge(int a,int b,int c) {
	adj[a].pb(mp(b,c));
	adj[b].pb(mp(a,c));
}
int dist[100005],pv[100005];
void dfs(int v,int d) {
	dist[v]=d;
	for (ii x:adj[v]) {
		if (dist[x.first]==INF) {
			pv[x.first]=v;
			dfs(x.first,max(d,x.second));
		}
	}
}
vector<int> path;
bool inside(int x,int a,int b) {
	return (x>=a && x<=b);
}
vector<int> vec;
int shortest_path(int a,int b) {
	if (dp[a]<dp[b]) swap(a,b);
	pv[a]=-1;
	for (int i=0;i<n;i++) dist[i]=INF;
	dfs(a,0);
	int c=b;
	path.clear();
	while(c!=-1) {
		path.pb(c);
		c=pv[c];
	}
	int onpath=INF;
	for (int i=1;i<sz(path)-1;i++) {
		for (ii x:fadj[path[i]]) {
			if (x.first==path[i-1] || x.first==path[i+1]) continue;
			onpath=min(onpath,x.second);
		}
	}
	int ans=max(dist[b],onpath);

	vec.clear();
	for (ii x:fadj[a]) {
		if (x.first==path[sz(path)-2]) continue;
		vec.pb(x.second);
	}
	sort(all(vec));
	if (sz(vec)>=2) {
		ans=min(ans,max(dist[b],vec[1]));
	}

	vec.clear();
	for (ii x:fadj[b]) {
		if (x.first==path[1]) continue;
		vec.pb(x.second);
	}
	sort(all(vec));
	if (sz(vec)>=2) {
		ans=min(ans,max(dist[b],vec[1]));
	}

	if (p[path[1]]==b) {
		for (auto edge:ne) {
			int w=edge.first;
			int ea=edge.second.first;
			int eb=edge.second.second;
			if (inside(pre[ea],pre[a],bd[a]) && inside(pre[eb],pre[a],bd[a])) continue;
			if (!inside(pre[ea],pre[path[1]],bd[path[1]]) && !inside(pre[eb],pre[path[1]],bd[path[1]])) continue;
			ans=min(ans,max(dist[b],w));
			break;
		}
	} else {
		for (auto edge:ne) {
			int w=edge.first;
			int ea=edge.second.first;
			int eb=edge.second.second;
			if (inside(pre[ea],pre[a],bd[a]) && inside(pre[eb],pre[a],bd[a])) continue;
			if (inside(pre[ea],pre[b],bd[b]) && inside(pre[eb],pre[b],bd[b])) continue;
			ans=min(ans,max(dist[b],w));
			break;
		}
	}
	return ans;
}

void mst() {
	sort(all(e));
	ufds u(n);
	for (int i=0;i<m;i++) {
		int a=e[i].second.first,b=e[i].second.second;
		fadj[a].pb(mp(b,e[i].first));
		fadj[b].pb(mp(a,e[i].first));

		if (!u.same(a,b)) {
			u.join(a,b);
			add_edge(a,b,e[i].first);
			// printf("add %d %d to Tree\n", a,b);
		} else {
			ne.pb(e[i]);
		}
	}
	p[0]=-1;
	form(0,0);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	n=N;
	m=M;
	for (int i=0;i<m;i++) {
		e.pb(mp(W[i],mp(U[i],V[i])));
	}
	mst();
}

int getMinimumFuelCapacity(int x, int y) {
	int ans=shortest_path(x,y);

	if (ans>=INF) return -1;
	return ans;
}

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