Submission #795760

#	Time	Username	Problem	Language	Result	Execution time	Memory
795760		bane	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1002 ms	66732 KiB

plan

#include<bits/stdc++.h>
using namespace std;

const int nax = (int)1e5 + 1;

list<int>comp[nax];
int l[nax], opasnost[nax], ans[nax];
vector<vector<pair<int,int>>>queries(nax), adj(nax);

inline int f(int a){
	if (l[a] == a)return  a;
	return l[a] = f(l[a]);
}

inline bool Merge(int a, int b, int c){
	a = f(a), b = f(b);
	if (a == b)return false;
	if (comp[a].size() < comp[b].size())swap(a,b);
	for (auto p : comp[b]){
		for (auto q : queries[p]){
			if (!ans[q.second] && f(q.first) == a){
				//cout << p << " " << q.first << endl;
				ans[q.second] = c;
			}
		}
	}
	comp[a].splice(comp[a].end(), comp[b]);
	l[b] = a;
	return true;
}

void solve(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>>edges;	
	for (int i = 0; i < n; i++){
		comp[i].push_back(i);
		l[i] = i;
		opasnost[i] = (int)1e9;
	}
	for (int i = 0; i < m; i++){
		int a,b,c;
		cin >> a >> b >> c;
		--a,--b;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
		edges.push_back({a,b,c});
	}

	int npp;
	cin >> npp;
	
	priority_queue<pair<int,int>>pq;
	for (int i = 0; i < npp; i++){
		int a; cin >> a; 
		--a;
		opasnost[a] = 0;
		pq.push({0,a});
	}

	while(!pq.empty()){
		int node = pq.top().second;
		int op = -pq.top().first;
		pq.pop();
		if (op != opasnost[node])continue;
		for (auto [x,w] : adj[node]){
			if (opasnost[x] > w + op){
				opasnost[x] = w + op;
				pq.push({-opasnost[x], x});
			}
		}
	}

	sort(edges.begin(), edges.end(), [&](auto x, auto y){
		return min(opasnost[x[0]], opasnost[x[1]]) > min(opasnost[y[0]], opasnost[y[1]]);
	});
	
	int qq;
	cin >> qq;
	for (int i = 0; i < qq; i++){
		int a,b;
		cin >> a >> b;
		--a,--b;
		queries[a].push_back({b,i});
		queries[b].push_back({a,i});
	}

	for (int i = 0; i < m; i++){
		//cout << edges[i][0] << " " << edges[i][1] << endl;
		Merge(edges[i][0], edges[i][1], min(opasnost[edges[i][0]], opasnost[edges[i][1]]));
	}

	for (int i = 0; i < qq; i++){
		cout << ans[i] << '\n';
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

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