Submission #565797

#	Time	Username	Problem	Language	Result	Execution time	Memory
565797		MrDeboo	Evacuation plan (IZhO18_plan)	C++17	100 / 100	2274 ms	95060 KiB

plan

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
pair<map<int,bool>,vector<pair<int,int>>>pr[100001];//have / need
map<pair<int,int>,int>ans;
int fath[100001];
int cur=0;
void merge(int a,int b){
    if(pr[a].second>pr[b].second)swap(pr[a],pr[b]);
    for(auto &i:pr[a].second){
        if(pr[b].first.count(i.first)){
            if(!ans.count({min(i.second,i.first),max(i.first,i.second)}))ans[{min(i.second,i.first),max(i.first,i.second)}]=cur;
        }
    }
    while(pr[a].second.size()){
        pr[b].second.push_back(pr[a].second.back());
        pr[a].second.pop_back();
    }
    if(pr[a].first.size()>pr[b].first.size())swap(pr[a].first,pr[b].first);
    for(auto &i:pr[a].first)pr[b].first[i.first]=1;
}
int dsu(int a){
    if(fath[a]==a)return a;
    int k=dsu(fath[a]);
    merge(a,k);
    return fath[a]=k;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)fath[i]=i;
    vector<pair<int,int>>vct[n+1];
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        vct[u].push_back({v,w});
        vct[v].push_back({u,w});
    }
    vector<int>dan(n+1,-1);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    int k;
    cin>>k;
    while(k--){
        int x;
        cin>>x;
        pq.push({0,x});
    }
    while(pq.size()){
        int b=pq.top().first,a=pq.top().second;
        pq.pop();
        if(dan[a]!=-1)continue;
        dan[a]=b;
        for(auto &i:vct[a]){
            if(dan[i.first]==-1){
                pq.push({b+i.second,i.first});
            }
        }
    }
    vector<int>need[n+1];
    vector<pair<int,int>>vcc;
    vector<pair<int,int>>vec;
    for(int i=1;i<=n;i++)vec.push_back({dan[i],i});
    sort(vec.begin(),vec.end(),greater<pair<int,int>>());
    int q;
    cin>>q;
    while(q--){
        int u,v;
        cin>>u>>v;
        vcc.push_back({u,v});
        need[u].push_back(v);
        need[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        pr[i].first[i]=1;
        for(auto &w:need[i])pr[i].second.push_back({w,i});
    }
    for(int i=0;i<n;i++){
        cur=vec[i].first;
        for(auto &w:vct[vec[i].second]){
            if(dan[w.first]<vec[i].first)continue;
            fath[dsu(vec[i].second)]=fath[dsu(w.first)];
            dsu(fath[dsu(vec[i].second)]);
        }
    }
    for(auto &i:vcc)cout<<ans[{min(i.first,i.second),max(i.first,i.second)}]<<endl;
}
/*
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: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46