Submission #167835

#	Time	Username	Problem	Language	Result	Execution time	Memory
167835		Dovran	Evacuation plan (IZhO18_plan)	C++11	0 / 100	1253 ms	35520 KiB

plan

#include <bits/stdc++.h>
#define N 500009
#define pii pair <int, int>
#define ff first
#define ss second
#define pb push_back
#define ll long long

using namespace std;

int n, m, k, ds[N], q, p[N], A[N];
bool vis[N];
vector<pii>e[N];
priority_queue<pii, vector<pii>, greater<pii>>Q;

int ata(int x){
	if(p[x]==x)
		return x;
	return p[x]=ata(p[x]);
}

void uni(int x, int y){
	p[ata(x)]=p[ata(y)];
}

void dsu(int x){
	for(auto i:e[x])
		if(vis[i.ff]==1)
			uni(x, i.ff);
}

int main(){
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		int a, b, c;
		cin>>a>>b>>c;
		e[a].pb({b, c});
		e[b].pb({a, c});
	}
	for(int i=1; i<=n; i++)
		ds[i]=1e9;
	cin>>k;
	for(int i=1; i<=k; i++){
		int a;
		cin>>a, Q.push({0, a}), ds[a]=0;
	} 
	while(Q.size()>0){
		int nd=Q.top().ss;
		Q.pop();
		if(vis[nd])
			continue;
		vis[nd]=1;
		for(auto i:e[nd]){
			int yol=i.ss;
			int to=i.ff;
			if(!vis[to] and ds[nd]+yol < ds[to])
				ds[to]=ds[nd]+yol, Q.push({ds[to], to});
		}
	}
	vector<pii>v;
	for(int i=1; i<=n; i++)
		 v.pb({ds[i], i});
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	cin>>q;
	for(int i=1; i<=q; i++){
		int a, b;
		cin>>a>>b;
		int l=0, r=v[0].ff;
		while(l<=r){
			int md=(l+r)/2;
			for(int j=1; j<=n; j++)
				p[j]=j;
			memset(vis, 0, sizeof(vis));

			int x=0;

			while(v[x].ff>=md){
				dsu(v[x].ss);
				vis[v[x].ss]=1;
				x++;
			}
			if(p[ata(a)]==p[ata(b)])
				l=md+1, A[i]=md;
			else
				r=md-1;
		}
		cout<<A[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: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46