Submission #644411

#	Time	Username	Problem	Language	Result	Execution time	Memory
644411		zxcvbnm	Evacuation plan (IZhO18_plan)	C++14	100 / 100	889 ms	41156 KiB

plan

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

constexpr int nax = 1e5 + 5;
constexpr int INF = 1e9 + 5;

#define w(x) cerr << (#x) << ": " << x << "\n";

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];
	vector<int> comp[nax];
	vector<pair<int, int>> vertex[nax];
	Dsu() {
		for(int i = 0; i < nax; i++) {
			par[i] = i;
			sz[i] = 1;
			comp[i].push_back(i);
			vertex[i].push_back({i, dist[i]});
		}
	}
	
	int find(int v) {
		if (par[v] == v) {
			return v;
		}
		return par[v] = find(par[v]);
	}
	
	void unite(int a, int b, int w) {
		a = find(a), b = find(b);
		if (a == b) return;
		
		if (sz[b] > sz[a]) {
			swap(a, b);
		}
				
		sz[a] += sz[b];
		for(int& i : comp[b]) {
			par[i] = a;
			comp[a].push_back(i);
			vertex[i].push_back({a, w});
		}
		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);
	
	//for(int i = 0; i < n; i++) {
		//cin >> dist[i];
	//}

	
	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;
	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]) {
				//cout << v << "->" << u.first << "\n";
				dsu.unite(v, u.first, dist[v]);
			}
		}
		
		//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 : qrs) {
		//int l = 0, r = max(dsu.vertex[i.first].size(), dsu.vertex[i.second].size())-1, idx = -1;
		
		//while(l <= r) {
			//int mid = (l + r) / 2;
			//int first = mid >= (int) dsu.vertex[i.first].size() ? 
			//dsu.vertex[i.first].back().first : dsu.vertex[i.first][mid].first;
			//int second = mid >= (int) dsu.vertex[i.second].size() ? 
			//dsu.vertex[i.second].back().first : dsu.vertex[i.second][mid].first;
			//if (first == second) {
				//idx = mid;
				//r = mid - 1;
			//}
			//else {
				//l = mid + 1;
			//}
		//}
		
		//int first = idx >= (int) dsu.vertex[i.first].size() ? 
		//dsu.vertex[i.first].back().second : dsu.vertex[i.first][idx].second;
		//int second = idx >= (int) dsu.vertex[i.second].size() ? 
		//dsu.vertex[i.second].back().second : dsu.vertex[i.second][idx].second;
		
		//ans.push_back(min({first, second, dist[i.first], dist[i.second]}));
		//assert(idx != -1);
		
		//w(idx);
		
		int add = 0;
		for(auto& x : dsu.vertex[i.first]) {
			for(auto& y : dsu.vertex[i.second]) {
				if (x.first == y.first) {
					add = max(add, min(x.second, y.second));
				}
			}
		}
		add = min({add, dist[i.first],  dist[i.second]});

		ans.push_back(add);
		
		//cout << i.first << " " << i.second << ": \n";
		//for(auto& j : dsu.vertex[i.first]) {
			//cout << j.first << " " << j.second << "\n";
		//}
		//cout << "---\n";
		//for(auto& j : dsu.vertex[i.second]) {
			//cout << j.first << " " << j.second << "\n";
		//}
	}
		
	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: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46