Submission #571732

#	Time	Username	Problem	Language	Result	Execution time	Memory
571732		duytuandao21	Evacuation plan (IZhO18_plan)	C++17	100 / 100	508 ms	130104 KiB

plan

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
const int N = 2e6+7;
int n,m,k,q,NNP[N],root[N],level[N],par[N][20],f[N][20],l[N],d[N];
vector<int> a[N];
vector<ii> adj[N];
struct DIS {
	int val;
	int idx;
};
DIS dist[N];
bool quick(const DIS x,const DIS y) {
	return x.val > y.val;
}
void DIJKSTRA() {
	priority_queue< ii, vector<ii>, greater<ii> > dt;
	for(int i=1;i<=n;i++) {
		if(NNP[i] == 1) {
			dist[i].val = 0;
			dt.push({0,i});
		}
	}
	while(!dt.empty()) {
		int u = dt.top().se;
		int value = dt.top().fi;
		dt.pop();
		if(dist[u].val != value) continue;
		for(ii w : adj[u]) {
			int v = w.se;
			int he = w.fi;

			if(dist[v].val > he + value) {
				dist[v].val = he + value;
				dt.push({dist[v].val, v});
			}
		}
	}
}
void buildLCA() {
	for(int k=1;k<=18;k++) {
		for(int i=1;i<=n;i++) {
			par[i][k] = par[par[i][k-1]][k-1];
			f[i][k] = min(f[i][k-1], f[par[i][k-1]][k-1]);
		}
	}
}
void DFS(int u) {
	for(int v : a[u]) {
		if(par[v][0] != 0) continue;
		par[v][0] = u;
		l[v] = l[u] + 1;
		f[v][0] = min(d[u], d[v]);
		DFS(v);
	}
}
int getLCA(int u,int v) {
	if(l[u] < l[v]) swap(u,v);
	int ans = 1e9+7;
	for(int k=18;k>=0;k--) {
		if(l[par[u][k]] >= l[v]) {
			ans = min(ans, f[u][k]);
			u = par[u][k];
		}
	}
	if(u==v) return ans;
	for(int k=18;k>=0;k--) {
		if(par[u][k] != par[v][k]) {
			ans = min(ans, min(f[u][k], f[v][k]));
			u = par[u][k];
			v = par[v][k];
		}
	}
	return min(ans, min(f[u][0], f[v][0]));
}
int get_root(int x) {
	if(root[x] == x) return x;
	return get_root(root[x]);
}
bool join(int x,int y) {
	int u = get_root(x);
	int v = get_root(y);
	if(u == v) return false;
	if(level[u] > level[v]) {
		root[v] = u;
		level[u] += level[v];
	} else {
		root[u] = v;
		level[v] += level[u];
	}
	return true;
}
void TREE() {
	sort(dist+1,dist+1+n,quick);
	vector<int> flag(n+1,0);
	for(int i=1;i<=n;i++) {
		int u = dist[i].idx;
		for(ii w : adj[u]){
			int v = w.se;
			if(flag[v] == 1) {
				if(join(u,v) == true) {
					a[u].push_back(v);
					a[v].push_back(u);
				}
			}
		}
		flag[u] = 1;
 	}
}
int main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back({w,v});
		adj[v].push_back({w,u});
	}
	cin>>k;
	while(k--) {
		int x;
		cin>>x;
		NNP[x] = 1;
	}
	for(int i=1;i<=n;i++) {
		dist[i].val = 1e9+7;
		dist[i].idx = i;
		root[i] = i;
		level[i] = 1;
	}
	DIJKSTRA();
	for(int i=1;i<=n;i++) d[i] = dist[i].val;
	TREE();
	par[1][0] = 1; f[1][0] = d[1]; DFS(1);
	buildLCA();
	cin>>q;
	while(q--) {
		int u,v;
		cin>>u>>v;
		cout<<getLCA(u,v)<<'\n';
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46