Submission #334792

#	Time	Username	Problem	Language	Result	Execution time	Memory
334792		amunduzbaev	Evacuation plan (IZhO18_plan)	C++14	100 / 100	833 ms	39520 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long 
#define ld long double 
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define prc(n) fixed << setprecision(n)
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi acos(-1);
const int inf = 1e9+7;
const int N = 1e5+5;

vector<pii>edges[N];
int dis[N], par[N], id[N], ans[N], used[N];
set<int>s[N];

bool cmp(int a, int b){
	return dis[a] > dis[b];
}

int find(int x){
	if(par[x] == x) return x;
	return par[x] = find(par[x]);
}

void merge(int x, int y, int v){
	if((x = find(x)) == (y = find(y))) return;
	if(sz(s[x]) < sz(s[y])) swap(x, y);
	for(set<int>::iterator it = s[y].begin(); it != s[y].end(); it++){
		if(s[x].count(*it)){
			ans[*it] = v;
			s[x].erase(*it);
		}
		else s[x].insert(*it);
	}
	s[y].clear();
	par[y] = x;
}

void solve(){
	int n, m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a, b, c;
		cin>>a>>b>>c;
		edges[a].pb({b, c});
		edges[b].pb({a, c});
	}
	
	for(int i=1;i<=n;i++) dis[i] = inf;
	
	int k;
	cin>>k;
	queue<int>qq;
	
	for(int i=0;i<k;i++){
		int a;
		cin>>a;
		dis[a] = 0;
		qq.push(a);
	}
	while(!qq.empty()){
		int cur = qq.front(); qq.pop();
		for(auto x:edges[cur]){
			if(x.ss + dis[cur] < dis[x.ff]){
				dis[x.ff] = x.ss + dis[cur];
				qq.push(x.ff);
			}
		}
	}	int q;
	cin>>q;
	for(int i=1;i<=q;i++){
		int a, b;
		cin>>a>>b;
		s[a].insert(i);
		s[b].insert(i);
	}
	for(int i=1;i<=n;i++){
		par[i] = id[i] = i;
	}
	sort(id+1, id+n+1, cmp);
	for(int i=1;i<=n;i++){
		used[id[i]] = 1;
		for(auto x : edges[id[i]]){
			if(used[x.ff]){
				merge(x.ff, id[i], dis[id[i]]);
			}
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	return;
}
/*

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

*/
int main(){
	fastios
	int t = 1;
	//cin>>t;
	while(t--) solve();
	return 0;
}

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