Submission #1129411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129411		Tsagana	Evacuation plan (IZhO18_plan)	C++20	100 / 100	781 ms	72016 KiB

plan

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

struct A {
	int a, w;
	bool operator<(const A& o)const{
		return w > o.w;
	}
};

struct B {
	int a, b, w;
	bool operator<(const B& o)const{
		return w > o.w;
	}
};

int p[100001];
int dis[100001];
int ans[100001];
vector<A> g[100001];
vector<B> edge;
set<int>  s[100001];
pq<A> q;

int find(int v) {return (v == p[v]) ? v : p[v] = find(p[v]);}

void solve () {
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) {dis[i] = 2e9; p[i] = i;}
	for (int i = 1; i <= m; i++) {
		int a, b, w; cin >> a >> b >> w;
		g[a].pb({b, w});
		g[b].pb({a, w});
	}
	int k; cin >> k;
	for (int i = 1; i <= k; i++) {
		int a; cin >> a;
		q.push({a, 0});
		dis[a] = 0;
	}
	int t; cin >> t;
	for (int i = 1; i <= t; i++) {
		int a, b; cin >> a >> b;
		s[a].insert(i);
		s[b].insert(i);
	}
	while (!q.empty()) {
		auto i = q.top(); q.pop();
		if (i.w > dis[i.a]) continue ;
		for (auto x: g[i.a]) {
			if (i.w + x.w >= dis[x.a]) continue ;
			q.push({x.a, i.w + x.w});
			dis[x.a] = i.w + x.w;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (auto x: g[i]) edge.pb({i, x.a, min(dis[i], dis[x.a])});
	}
	sort(all(edge));
	for (auto e: edge) {
		e.a = find(e.a);
		e.b = find(e.b);
		if (e.a == e.b) continue ;
		if (s[e.a].size() > s[e.b].size()) swap(e.a, e.b);
		for (auto x: s[e.a]) {
			if (s[e.b].count(x)) {
				ans[x] = e.w;
				s[e.b].erase(x);
			}
			else s[e.b].insert(x);
		}
		p[e.a] = p[e.b];
	}
	for (int i = 1; i <= t; i++) cout << ans[i] << '\n';
}
signed main() {IOS solve(); return 0;}

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