Submission #1131751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131751		why1	Evacuation plan (IZhO18_plan)	C++20	100 / 100	408 ms	52624 KiB

plan

#include <bits/stdc++.h>
using namespace std;

#define ll unsigned long long
#define pb push_back
#define pii pair<int,int>
#define sz size()
#define all(v) v.begin(),v.end()
#define fi first
#define se second

const int N = 1e5;
const int mod = 1e9+7;
const int INF = 1e9;

const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};

int n,m,k;
vector<pii> g[N+1];
set<int> st[N+1];
int ans[N+1],p[N+1],d[N+1];

int get(int v){
	if(v!=p[v])
		p[v]=get(p[v]);
	return p[v];
}

void merge(int a,int b,int val){
	a=get(a);
	b=get(b);
	if(a!=b){
		if(st[a].sz<st[b].sz)
			st[a].swap(st[b]);
		for(auto i: st[b]){
			if(st[a].find(i)!=st[a].end()){
				ans[i]=val;
				st[a].erase(i);
			}
			else
				st[a].insert(i);
		}
		p[b]=a;
	}
}

void solve() {
	cin>>n>>m;
	for(int i = 1; i <= m; i++){
		int x,y,c;
		cin>>x>>y>>c;
		g[x].pb({y,c});
		g[y].pb({x,c});
	}
	cin>>k;
	set<pii> st_d;
	for(int i = 1; i <= n; i++){
		d[i]=INF;
		p[i]=i;
	}
	for(int i = 1; i <= k; i++){
		int x;
		cin>>x;
		d[x]=0;
		st_d.insert({d[x],x});
	}
	int q;
	cin>>q;
	for(int i = 1; i <= q; i++){
		int x,y;
		cin>>x>>y;
		st[x].insert(i);
		st[y].insert(i);
	}
	while(!st_d.empty()){
		int v=st_d.begin()->se;
		st_d.erase(st_d.begin());
		for(auto [to,c]: g[v]){
			if(d[to]>d[v]+c){
				st_d.erase({d[to],to});
				d[to]=d[v]+c;
				st_d.insert({d[to],to});
			}
		}
	}
	vector<pii> v;
	for(int i = 1; i <= n; i++){
		v.pb({d[i],i});
	}
	sort(v.rbegin(),v.rend());
	for(auto [val,i]: v){
		for(auto [to,c]: g[i]){
			if(d[to]>=d[i]){
				merge(i,to,d[i]);
			}
		}
	}
	for(int i = 1; i <= q; i++){
		cout<<ans[i]<<"\n";
	}
}

int main() {

	//freopen("cowrun.in","r",stdin);
	//freopen("cowrun.out","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    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