Submission #644405

#	Time	Username	Problem	Language	Result	Execution time	Memory
644405		zxcvbnm	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4046 ms	26212 KiB

plan

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

constexpr int nax = 1e5 + 5;
constexpr int INF = 1e9 + 5;
vector<pair<int, int>> adj[nax];

int dist[nax];

void dijkstra(vector<int>& src) {
	for(int i = 0; i < nax; i++) {
		dist[i] = INF;
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	for(int& i : src) {
		q.push({i, 0});
		dist[i] = 0;
	}
	
	while(!q.empty()) {
		auto v = q.top();
		//cout << v.first << " " << v.second << "\n";
		q.pop();
		
		if (v.second != dist[v.first]) continue;
		
		for(auto u : adj[v.first]) {
			int cost = v.second + u.second;
			if (dist[u.first] > cost) {
				dist[u.first] = cost;
				q.push({u.first, dist[u.first]});
			}
		}
	}
}

struct Dsu {
	int par[nax];
	int sz[nax];
	
	Dsu() {
		for(int i = 0; i < nax; i++) {
			par[i] = i;
			sz[i] = 1;
		}
	}
	
	int find(int v) {
		if (par[v] == v) {
			return v;
		}
		return par[v] = find(par[v]);
	}
	
	void unite(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return;
		
		if (sz[b] > sz[a]) {
			swap(a, b);
		}
		
		sz[a] += sz[b];
		par[b] = a;
	}
	
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	
	for(int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		a--, b--;
		adj[a].push_back({b, w});
		adj[b].push_back({a, w});
	}
	
	int k;
	cin >> k;
	vector<int> src(k);
	for(int& i : src) {
		cin >> i;
		i--;
	}
	
	dijkstra(src);
	
	vector<int> order(n);
	iota(order.begin(), order.end(), 0);
	
	sort(order.begin(), order.end(), [&](int x, int y) {
		return dist[x] > dist[y];
	});
	
	Dsu dsu;
	
	int q;
	cin >> q;
	
	vector<pair<int, int>> qrs(q);
	vector<int> ans(q, 0);
	for(auto& i : qrs) {
		cin >> i.first >> i.second;
		i.first--, i.second--;
	}

	for(int& v : order) {
		for(auto u : adj[v]) {
			if (dist[v] <= dist[u.first])
				dsu.unite(v, u.first);
		}
		
		for(int i = 0; i < q; i++) {
			if (dsu.find(qrs[i].first) == dsu.find(qrs[i].second)) {
				ans[i] = max(ans[i], dist[v]);
			}
		}
	}
	
	for(auto& i : ans) {
		cout << i << "\n";
	}
	
	//for(int i : order) {
		//cout << i << "\n";
	//}
	
	//for(int i = 0; i < n; i++) {
		//cout << i << ": " << dist[i] << "\n";
	//}
	
	
}

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