Submission #1280857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280857		WH8	Evacuation plan (IZhO18_plan)	C++20	100 / 100	845 ms	47384 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double


signed main(){
	int n,m;cin>>n>>m;
	vector<vector<pair<int,int>>> al(n+1);
	vector<pair<int,int>> ed;
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		al[a].pb({b,c});
		al[b].pb({a, c});
		ed.pb({a,b});
	}
	int k;cin>>k;
	priority_queue<pll, vector<pll>,greater<pll>> pq;
	vector<int> dist(n+1, 1e15);
	for(int i=0;i<k;i++){
		int c;cin>>c;
		dist[c]=0;
		pq.push({0, c});
	}
	while(!pq.empty()){
		auto [d, c] =pq.top();pq.pop();
		if(dist[c]<d)continue;
		for(auto [to, w] : al[c]){
			if(dist[to] > w+d){
				dist[to]=w+d;
				pq.push({w+d, to});
			}
		}
	}
	sort(ed.begin(),ed.end(), [&](auto a, auto b){
		return min(dist[a.f], dist[a.s]) > min(dist[b.f], dist[b.s]);
	});
	//~ for(int i=1;i<=n;i++){
		//~ printf("dist of %lld is %lld\n",i,dist[i]);
	//~ }
	vector<int> p(2*n+5, 0);
	auto par=[&](auto par, int x) -> int{
		if(p[x]==0)return x;
		return p[x]=par(par,p[x]);
	};
	int q;cin>>q;
	vector<pair<int,int>> qs(q);
	vector<int> ans(q, 0);
	for(int i=0;i<q;i++)cin>>qs[i].f>>qs[i].s;
	queue<tuple<int,int,vector<int>>> bs; 
	vector<int> temp(q); iota(temp.begin(),temp.end(),0ll);
	//~ for(auto it:temp)cout<<it<<endl;
	bs.push({-1, m-1, temp});
	int ptr=0;
	while(!bs.empty()){
		int l=get<0>(bs.front()), r=get<1>(bs.front());
		//~ printf("%lld %lld\n",l,r);
		vector<int> cq=get<2>(bs.front());
		bs.pop();
		if(l==r-1){
			for (auto qind : cq){
				ans[qind]=min(dist[ed[r].f], dist[ed[r].s]);
			}
			continue;
		}
		vector<int> lo, hi;
		int m=(l+r)/2;
		if(m < ptr){
			// reset
			p.assign(n+1, 0);
			ptr=0;
		}
		while (ptr <= m){
			int pa=par(par, ed[ptr].f), pb=par(par, ed[ptr].s);
			if(pa!=pb){
				//~ printf("merging %lld and %lld\n", pa, pb);
				p[pa]=pb;
			}
			ptr++;
		}
		for(auto qind:cq){
			int pa=par(par,qs[qind].f), pb=par(par,qs[qind].s);
			//~ printf("qind %lld has %lld and %lld\n", qind,pa,pb);
			if(pa==pb){
				lo.pb(qind);
			}
			else hi.pb(qind);
		}
		if(!lo.empty())bs.push({l,m,lo});
		if(!hi.empty())bs.push({m,r,hi});
	}
	for(int i=0;i<q;i++){
		cout<<ans[i]<<"\n";
	}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/
		

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