Submission #512231

#	Time	Username	Problem	Language	Result	Execution time	Memory
512231		sidpark1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	648 ms	94040 KiB

plan

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define F first
#define S second

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>

const int mxN = 1e5 + 5; 
const int INF = 1e9 + 7; 
int n,m;
int k;
int q;
int ans;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<vector<pair<int,int>>> adj(mxN);
vector<array<int,3>> edges;
vector<int> dist(mxN, INF);
vector<int> sz(mxN, 1), leader(mxN);
vector<int> npp;
int cnt = 1;
const int LOG = 21;
bool is_npp[mxN];
int tin[mxN], tout[mxN], depth[mxN];
int up[mxN][LOG], mpath[mxN][LOG];

int root(int z) {
	if(z == leader[z]) return z;
	return (leader[z] = root(leader[z]));
}

void unite(int x, int y) {
	x = root(x), y = root(y);
	if(x == y) return;
	if(sz[x] < sz[y]) swap(x,y);
	sz[x] += sz[y];
	leader[y] = x;
}

bool ancestor(int x, int y) {
	return (tin[x] <= tin[y] and tout[x] >= tout[y]);
}

void dfs(int x, int p, int w) {
	tin[x] = ++cnt;
	up[x][0] = p;
	mpath[x][0] = w;

	for(int i=1; i<=LOG-1; i++) {
		up[x][i] = up[up[x][i-1]][i-1];
		mpath[x][i] = min(mpath[up[x][i-1]][i-1], mpath[x][i-1]);
	}

	for(auto z : adj[x]) {
		if(z.F != p) {
			depth[z.F] = depth[x] + 1;
			dfs(z.F, x, z.S);
		}
	}

	tout[x] = ++cnt;
}


int get_lca(int x, int y) {

	if(ancestor(x,y)) {
		return x;
	}

	for(int i=LOG-1; i>=0; i--) {
		if(!ancestor(up[x][i],y)) {
			x = up[x][i];
		}
	}

	return up[x][0];
}

void compute(int x, int y) {

	if(tin[x] > tin[y]) {
		swap(x,y);
	}

	ans = min(dist[x], dist[y]);


	int lca = get_lca(x,y);

	for(int i=LOG-1; i>=0; i--) {
		if(!ancestor(up[x][i], lca)) {
			ans = min(ans, mpath[x][i]);
			x = up[x][i];
		}
	}

	//ans = min(ans, mpath[x][0]);

	if(!ancestor(x,lca)) {
		ans = min(ans, mpath[x][0]);
	}

	if(lca == y) return;

	for(int i=LOG-1; i>=0; i--) {
		if(!ancestor(up[y][i],lca)) {
			ans = min(ans, mpath[y][i]);
			y = up[y][i];
		}
	}

	if(!ancestor(y,lca)) {
		ans = min(ans, mpath[y][0]);
	}


	
}

void solve() {

	cin >> n >> m;

	for(int i=1,u,v,w; i<=m; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
		edges.push_back({w,u,v});
	}

	cin >> k;

	for(int i=1,z; i<=k; i++) {
		cin >> z;
		npp.push_back(z);
		is_npp[z] = true;
		dist[z] = 0;
		pq.push({0,z});
	}

	while(!pq.empty()) {
		pair<int,int> kch = pq.top();
		pq.pop();
		if(dist[kch.S] == kch.F) {
			for(auto z : adj[kch.S]) {
				if(dist[kch.S] + z.S < dist[z.F]) {
					dist[z.F] = dist[kch.S] + z.S;
					pq.push({dist[z.F], z.F});
				}
			}
		}
	}

	for(int i=0; i<m; i++) {
		edges[i][0] = min(dist[edges[i][1]], dist[edges[i][2]]);
	}

	sort(edges.begin(), edges.end());
	reverse(edges.begin(), edges.end());

	for(int i=1; i<=n; i++) {
		adj[i].resize(0);
		adj[i].clear();
		leader[i] = i;
	}

	for(int i=0; i<m; i++) {
		if(root(edges[i][1]) == root(edges[i][2])) continue;
		unite(edges[i][1], edges[i][2]);
		adj[edges[i][1]].push_back({edges[i][2], edges[i][0]});
		adj[edges[i][2]].push_back({edges[i][1], edges[i][0]});
	}


	int q;
	cin >> q;

	dfs(1,1, dist[1]);

	while(q--) {

		int u,v;
		cin >> u >> v;

		compute(u,v);

		cout << ans << '\n';
	}
	
	

}

signed main() {

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int tc = 1;

	while(tc--) {

		solve();

	}
}

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