Submission #1283369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283369		Jawad_Akbar_JJ	Evacuation plan (IZhO18_plan)	C++20	41 / 100	4088 ms	61212 KiB

plan

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
#define int long long
const int N = 1<<17;
vector<pair<int,int>> nei[N], E, Ew;
set<int> vec[N];
int Min[N], Ans[N], Par[N], inf = 1e17;

void dijkstra(int n, int k = 0){
	for (int i=1;i<=n;i++)
		Min[i] = inf;

	set<pair<int,int>> st;
	cin>>k;
	for (int i=1, v;i<=k;i++)
		cin>>v, Min[v] = 0, st.insert({0, v});

	while (st.size() > 0){
		auto [mn, u] = *begin(st);
		st.erase(begin(st));

		for (auto [i, w] : nei[u]){
			if (mn + w < Min[i]){
				st.erase({Min[i], i});
				Min[i] = mn + w;
				st.insert({Min[i], i});
			}
		}
	}
}

int root(int v){
	if (Par[v] == v)
		return v;
	return (Par[v] == 0 ? v : Par[v] = root(Par[v]));
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, k, q;
	cin>>n>>m;

	for (int i=1, a, b, l;i<=m;i++){
		cin>>a>>b>>l;
		nei[a].push_back({b, l});
		nei[b].push_back({a, l});
		E.push_back({a, b});
	}

	dijkstra(n);

	for (int i=0;i<m;i++)
		Ew.push_back({min(Min[E[i].second], Min[E[i].first]), i});
	sort(rbegin(Ew), rend(Ew));

	cin>>q;
	for (int i=1, s, t;i<=q;i++){
		cin>>s>>t;
		vec[s].insert(i);
		vec[t].insert(i);
	}

	for (auto [w, id] : Ew){
		int A = root(E[id].first), B = root(E[id].second);

		if (A == B)
			continue;
		if (vec[A].size() > vec[B].size())
			swap(A, B);

		for (int i : vec[B]){
			if (vec[A].find(i) != vec[A].end())
				Ans[i] = w, vec[A].erase(i);
			else
				vec[A].insert(i);
		}
		set<int> ().swap(vec[B]);
		Par[B] = A;
	}
	for (int i=1;i<=q;i++)
		cout<<Ans[i]<<' ';
	cout<<'\n';
}

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