Submission #713713

#	Time	Username	Problem	Language	Result	Execution time	Memory
713713		Ahmed57	Evacuation plan (IZhO18_plan)	C++14	100 / 100	732 ms	67076 KiB

plan

#include <bits/stdc++.h>

using namespace std;
vector<pair<long long,long long>> adj[100001],tree[100001];
vector <long long> cost(100001,1e18);
int pr[100001];
int gs[100001];
int P[100001][18];
int hi[100001];
int val[100001][18];
int findleader(int x){
    if(pr[x]==x){
        return x;
    }
    return pr[x] = findleader(pr[x]);
}
bool mergegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    if(led1==led2)return 0;
    if(gs[led1]>gs[led2]){
        pr[led2]=led1;
        gs[led1]+=gs[led2];
    }else{
        pr[led1]=led2;
        gs[led2]+=gs[led1];
    }
    return 1;
}
void d(vector<int>no){
    priority_queue<pair<long long,long long>> q1;
    for(auto i:no){
        q1.push({0,i});
        cost[i] = 0;
    }
    while(!q1.empty()){
        long long co = q1.top().first*-1;
        long long no = q1.top().second;
        q1.pop();
        if (co>cost[no]) continue ;
        for(int i= 0;i<tree[no].size();i++){
            if(cost[tree[no][i].first]>(tree[no][i].second+co)){
                cost[tree[no][i].first] = (tree[no][i].second+co);
                q1.push({cost[tree[no][i].first]*-1,tree[no][i].first});
            }
        }
    }
}
void dfs(int node,int pa){
    P[node][0]=pa;
    hi[node]=hi[pa]+1;
    val[node][0] = min(cost[node],cost[pa]);
    for(int k=1;k<=17;k++){
        P[node][k]=P[P[node][k-1]][k-1];
        val[node][k] = min(val[node][k-1],val[P[node][k-1]][k-1]);
    }
    for(auto i:adj[node])
    {
        if(i.first==pa)continue;
        dfs(i.first,node);
    }
}

int lca(int x,int y)
{
    int ans = 1e9;
    if(hi[x]<hi[y]) swap(x,y);
    for(int k=17;k>=0;k--)
    {
        if(hi[x]-(1<<k) >= hi[y]){
            ans= min(ans,val[x][k]);
            x=P[x][k];
        }
    }
    if(x==y) return ans;
    for(int k=17;k>=0;k--)
    {
        if(P[x][k] != P[y][k]){
            ans =  min({ans,val[x][k],val[y][k]});
            x=P[x][k],y=P[y][k];
        }
    }
    return min({ans,val[x][0],val[y][0]});
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i= 1;i<=n;i++)pr[i]= i,gs[i] = 1;
    vector<pair<int,pair<int,int>>> ed;
    for(int i = 0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        tree[a].push_back({b,c});
        tree[b].push_back({a,c});
        ed.push_back({c,{a,b}});
    }
    int k;cin>>k;vector<int> nodes;
    for(int i = 0;i<k;i++){
        int x;cin>>x;
        nodes.push_back(x);
    }
    d(nodes);
    for(int i= 0;i<ed.size();i++){
        ed[i].first=min(cost[ed[i].second.first],cost[ed[i].second.second]);
    }
    sort(ed.begin(),ed.end());
    reverse(ed.begin(),ed.end());
    for(auto i:ed){
        if(mergegroup(i.second.first,i.second.second)){
            adj[i.second.first].push_back({i.second.second,i.first});
            adj[i.second.second].push_back({i.second.first,i.first});
        }
    }
    dfs(1,1);
    int q;cin>>q;
    while(q--){
        int l,r;cin>>l>>r;
        if(l==r)cout<<cost[l]<<endl;
        else cout<<lca(l,r)<<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
*/

Compilation message (stderr)

plan.cpp: In function 'void d(std::vector<int>)':
plan.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i= 0;i<tree[no].size();i++){
      |                      ~^~~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:104:19: 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]
  104 |     for(int i= 0;i<ed.size();i++){
      |                  ~^~~~~~~~~~

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