Submission #391366

#	Time	Username	Problem	Language	Result	Execution time	Memory
391366		ritul_kr_singh	Evacuation plan (IZhO18_plan)	C++17	100 / 100	860 ms	61576 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
#define v e.first
#define w e.second

const int MAXN = 1e5, INF = 1e18;
vector<vector<pair<int, int>>> g(MAXN);
vector<int> par(MAXN), d(MAXN, INF);

int find(int u){
	return par[u] == u ? u : par[u] = find(par[u]);
}

bool comp(int a, int b){
	return d[a] > d[b];
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, x, y, z; cin >> n >> m;
	while(m--){
		cin >> x >> y >> z; --x, --y;
		g[x].emplace_back(y, z);
		g[y].emplace_back(x, z);
	}

	priority_queue<pair<int, int>> q;

	cin >> z;
	while(z--){
		cin >> x; --x;
		d[x] = 0;
		q.emplace(0, x);
	}

	while(!q.empty()){
		int u = q.top().second, dist = -q.top().first; q.pop();
		if(dist != d[u]) continue;
		for(auto &e : g[u])
			if(d[v] > dist + w) q.emplace(-(d[v] = dist + w), v);
	}

	vector<set<int>> groups(n);



	cin >> z;
	for(int i=0; i<z; ++i){
		cin >> x >> y; --x, --y;
		groups[x].insert(i);
		groups[y].insert(i);
	}

	vector<int> cities(n), ans(z);
	iota(cities.begin(), cities.end(), 0LL);
	sort(cities.begin(), cities.end(), comp);

	vector<int> pos(n);
	for(int i=0; i<n; ++i) pos[cities[i]] = i;

	iota(par.begin(), par.begin()+n, 0LL);

	for(int u : cities){
		// cout << u+1 sp d[u] sp "..." nl;
		z = u;
		u = find(u);
		for(auto &e : g[u]){
			if(pos[v] > pos[z]) continue;
			x = find(v);
			if(groups[x].size() > groups[u].size()) swap(groups[x], groups[u]);
		}
		for(auto &e : g[u]){
			if(pos[v] > pos[z]) continue;
			x = find(v);
			if(x == u) continue;
			for(int i : groups[x]){
				if(groups[u].find(i) != groups[u].end()){
					ans[i] = d[u];
					// cout << u+1 sp d[u] nl;
				}else groups[u].insert(i);
			}
			par[x] = u;
		}
	}

	for(int i : ans) cout << i nl;
}

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