Submission #525327

#	Time	Username	Problem	Language	Result	Execution time	Memory
525327		Mr_Husanboy	Evacuation plan (IZhO18_plan)	C++14	100 / 100	656 ms	60576 KiB

plan

// Muallif: Mansuraliyev Husanboy Murotali o'g'li  >> NamPS

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define F first
#define S second
// 0-9 >> 48-57;    A-Z>>65-90   and   a-z>>97-122 respectively;	
int l[100005];
vector<pair<int,int>> g[100005];
set<int> st[100005];

void init(int n){
	for(int i=1;i<=n;i++) l[i]=i;
}

int get(int a){
	if(l[a]==a){
		return a;
	}
	return l[a]=get(l[a]);
}


void solve(){
	int n,m; cin>>n>>m;
	init(n);
	for(int i=0;i<m;i++){
		int u,v,w; cin>>u>>v>>w;
		g[u].push_back({v,w});g[v].push_back({u,w});
	}
	int dist[n+1];
	bool vis[n+1];
	for(int i=1;i<=n;i++) dist[i]=1e9,vis[i]=0;
	priority_queue<pair<int,int>> q;
	int k; cin>>k;while(k--){
		int x; cin>>x; dist[x]=0; q.push({0,x});
	}
	while(!q.empty()){
		int t=q.top().second; q.pop();
		if(vis[t]) continue; vis[t]=1;
		for(auto u:g[t]){
			if(dist[u.F]>dist[t]+u.S){
				dist[u.F]=dist[t]+u.S;
				q.push({-dist[u.F],u.F});
			}
		}
	}
	int qq; cin>>qq;
	for(int i=0;i<qq;i++){
		int x,y; cin>>x>>y; st[x].insert(i);st[y].insert(i);
	}
	vector<pair<int,pair<int,int>>> v;
	for(int i=1;i<=n;i++){
		for(auto u:g[i]){
			v.push_back({min(dist[i],dist[u.F]),{i,u.F}});
		}
	}
	sort(all(v));
	vector<int> ans(qq);
	reverse(all(v));
	for(int i=0;i<v.size();i++){
		int x=v[i].S.F,y=v[i].S.S,w=v[i].F;
		//cout<<x<<' '<<y<<' '<<w<<'\n';
		x=get(x),y=get(y);
		if(x==y) continue;
		if(st[x].size() < st[y].size())
			swap(x, y);
		for(auto u:st[y]){
			if(st[x].count(u)){
				ans[u]=w;
				st[x].erase(u);
			}else st[x].insert(u);
		}l[y]=x;
	}
	for(auto u:ans) cout<<u<<'\n';
}


int main(){
	ios; 
	//int t=1;   cin>>t; while(t--)
	solve();
}
/*
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
*/

Compilation message (stderr)

plan.cpp: In function 'void solve()':
plan.cpp:44:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |   if(vis[t]) continue; vis[t]=1;
      |   ^~
plan.cpp:44:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |   if(vis[t]) continue; vis[t]=1;
      |                        ^~~
plan.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<v.size();i++){
      |              ~^~~~~~~~~

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