Submission #1093087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093087		4QT0R	Evacuation plan (IZhO18_plan)	C++17	100 / 100	406 ms	78700 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>

vector<pll> graph[100003];
array<ll,3> edges[500003];
ll dist[100003];
bool NPP[100003];
ll oo=1e18;

void Dijkstra(ll n){
	priority_queue<pll,vector<pll>,greater<pll>> pq;
	fill(dist,dist+n+1,oo);
	for (ll i = 1; i<=n; i++)if (NPP[i]){
		dist[i]=0;
		pq.push({0,i});
	}
	while(pq.size()){
		auto [d,v] = pq.top();
		pq.pop();
		if (d!=dist[v])continue;
		for (auto [u,c] : graph[v]){
			if (d+c<dist[u]){
				dist[u]=d+c;
				pq.push({dist[u],u});
			}
		}
	}
}

ll lider[100003];
ll siz[100003];
ll Find(ll v){
	return lider[v]==v?lider[v]:(lider[v]=Find(lider[v]));
}
void Union(ll a, ll b){
	a=Find(a);
	b=Find(b);
	if (a==b)return;
	if (siz[a]<siz[b])swap(a,b);
	lider[b]=a;
	siz[a]+=siz[b];
}

struct zap{
	ll l;
	ll p;
	ll st;
	ll nd;
};
vector<ll> query[100003];
zap dane[500003];
vector<ll> dl;

ll ans[500003];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	ll n,m,k,q;
	cin >> n >> m;
	for (ll i = 1; i<=m; i++){
		cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
		graph[edges[i][0]].push_back({edges[i][1],edges[i][2]});
		graph[edges[i][1]].push_back({edges[i][0],edges[i][2]});
	}
	cin >> k;
	for (ll i = 1,v; i<=k; i++){
		cin >> v;
		NPP[v]=true;
	}
	Dijkstra(n);
	for (ll i = 1; i<=m; i++)edges[i][2]=min(dist[edges[i][0]],dist[edges[i][1]]);
	sort(edges+1,edges+m+1,[](array<ll,3> a, array<ll,3> b){return a[2]>b[2];});
	dl.push_back(-1);
	for (ll i = 1; i<=n; i++)dl.push_back(dist[i]);
	sort(dl.begin(),dl.end());
	cin >> q;
	for (ll i = 1; i<=q; i++){
		cin >> dane[i].st >> dane[i].nd;
		dane[i].l=0;
		dane[i].p=dl.size()-1;
		query[dl.size()/2].push_back(i);
	}
	ll lft=q;
	while(lft){
		for (ll i = 1; i<=n; i++){
			lider[i]=i;
			siz[i]=1;
		}
		ll iter=1;
		for (ll i = dl.size()-1; i>=0; i--){
			while(iter<=m && edges[iter][2]>=dl[i]){
				Union(edges[iter][0],edges[iter][1]);
				iter++;
			}
			while(query[i].size()){
				ll now=query[i].back();
				query[i].pop_back();
				if (dane[now].l==dane[now].p){
					ans[now]=dl[i];
					lft--;
					continue;
				}
				if (Find(dane[now].st)==Find(dane[now].nd))dane[now].l=i;
				else dane[now].p=i-1;
				query[(dane[now].l+dane[now].p+1)/2].push_back(now);
			}
		}
	}
	for (ll i = 1; i<=q; i++)cout << ans[i] << '\n';
}

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