Submission #168477

#	Time	Username	Problem	Language	Result	Execution time	Memory
168477		David_M	Evacuation plan (IZhO18_plan)	C++17	0 / 100	394 ms	20876 KiB

plan

#include <bits/stdc++.h>
//#include <iostream>
#define F first
#define S second
#define ll long long
#define pb push_back
using namespace std; 
const ll N=100005, INF=1e17;
ll n, m, k, d[N], a[N], b[N], Q, x, y, c, Ans[N], mid[N], F[N], l[N], r[N], ans1, ans2, Pa[N], w[N], t;
vector <pair<int, int> > v[N], V;
vector <ll> D[2001];
priority_queue <pair<int, int> > q;
void clear(){V.clear();
	for (int j=1; j<=Q; j++){
		mid[j]=(l[j]+r[j])>>1;
		V.pb({mid[j], j});
	}sort(V.begin(), V.end());reverse(V.begin(), V.end());
	t=1001;
	for (int i=1; i<=n; i++)Pa[i]=i, w[i]=1, F[i]=0;
}
int PA(int x){
	if(x==Pa[x])return x; else return Pa[x]=PA(Pa[x]); 
}
void upd(pair<int, int> A){
	A.F=PA(A.F);
	A.S=PA(A.S);
	if(A.F!=A.S){
		if(w[A.F]>w[A.S]){swap(A.F, A.S); }
		Pa[A.F]=A.S;
		w[A.S]+=w[A.F];
	}
}
int main(){
	cin>>n>>m;
	for (int i=1; i<=n; i++)d[i]=INF;
	for (int i=1; i<=m; i++)
		cin>>x>>y>>c,
		v[x].pb({y, c}),
		v[y].pb({x, c});
	cin>>k;
	for (int i=1; i<=k; i++)cin>>x,q.push({x,0}),d[x]=0;
	while(!q.empty()){
		int x=(q.top()).F;q.pop();
		for (int i=0; i<(int)v[x].size(); i++){
			if(d[v[x][i].F]==INF)q.push({v[x][i].F, d[x]+v[x][i].S});
			d[v[x][i].F]=min(d[v[x][i].F], d[x]+v[x][i].S);
		}
	}
	for (int i=1; i<=n; i++)D[d[i]].pb(i);

	cin>>Q;
	for (int i=1; i<=Q; i++) cin>>a[i]>>b[i], l[i]=0, r[i]=1001;
	for (int i=1; i<=20; i++){
		clear();
		for (int j=0; j<Q; j++){
			while(t>V[j].F){
				for (int e=0; e<(int)D[t].size(); e++){
					F[D[t][e]]=1;
					for (int u=0; u<(int)v[D[t][e]].size(); u++)
						if(F[v[D[t][e]][u].F])upd({D[t][e], v[D[t][e]][u].F});
				}
				t--;
			}
			if(PA(a[V[j].S])==PA(b[V[j].S])){
				Ans[V[j].S]=mid[V[j].S]; l[V[j].S]=mid[V[j].S]+1;
			}else r[V[j].S]=mid[V[j].S]-1;
		}
	}
	for (int i=1; i<=Q; i++)
		cout<<Ans[i]+1<<'\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: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46