Submission #334336

#TimeUsernameProblemLanguageResultExecution timeMemory
334336juggernautEvacuation plan (IZhO18_plan)C++14
0 / 100
239 ms18712 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,dis[100005],par[100005],sz[100005],up[100005][17],mn[100005][17],tin[100005],tout[100005],timer;
struct data{
    int x,y,z;
};
int fin(int v){
    return v==par[v]?v:par[v]=fin(par[v]);
}
vector<pair<int,int>>g[100005];
void dfs(int v,int p,int val){
    tin[v]=++timer;
    up[v][0]=p;
    mn[v][0]=val;
    for(int i=1;i<17;i++){
        up[v][i]=up[up[v][i-1]][i-1];
        mn[v][i]=min(mn[v][i-1],mn[up[v][i-1]][i-1]);
    }
    for(auto to:g[v])if(to.first!=p)dfs(to.first,v,to.second);
    tout[v]=++timer;
}
bool upper(int a,int b){
	return tin[a]<=tin[b]&&tout[a]>=tout[b];
}
vector<data>edge,vec;
int lca(int a,int b){
    if(upper(a,b))return a;
    if(upper(b,a))return b;
    for(int i=16;i>=0;i--)
    if(!upper(up[a][i],b))a=up[a][i];
    return up[a][0];
}
bool cmp(data l,data r){
    return l.z>r.z;
}
int go(int v,int l){
    int res=2e9;
    for(int i=16;i>=0;i--){
        if(!upper(v,l)){
            res=min(res,mn[v][i]);
            v=up[v][i];
        }
    }
    res=min(res,mn[v][0]);
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        data e;
        scanf("%d%d%d",&e.x,&e.y,&e.z);
        edge.push_back(e);
        g[e.x].push_back({e.y,e.z});
        g[e.y].push_back({e.x,e.z});
    }
    for(int i=1;i<=n;i++)dis[i]=2e9;
    scanf("%d",&m);
    priority_queue<pair<int,int>>q;
    while(m--){
        int x;
        scanf("%d",&x);
        dis[x]=0;
        q.push({0,x});
    }
    while(!q.empty()){
        int v=q.top().second;
        int val=-q.top().first;
        q.pop();
        if(val>dis[v])continue;
        for(auto to:g[v]){
            if(dis[to.first]>val+to.second){
                dis[to.first]=val+to.second;
                q.push({-dis[to.first],to.first});
            }
        }
    }
    for(int i=1;i<=n;i++){
        sz[i]=1,par[i]=i;
        g[i].clear();
    }
    for(auto to:edge){
        data e;
        e=to;
        e.z=min(dis[to.x],dis[to.y]);
        vec.push_back(e);
    }
    sort(vec.begin(),vec.end(),cmp);
    for(auto to:vec){
        int x=fin(to.x);
        int y=fin(to.y);
        if(x!=y){
            if(sz[x]<sz[y])swap(x,y);
            sz[x]+=sz[y];
            par[y]=x;
            g[to.x].push_back({to.y,to.z});
            g[to.y].push_back({to.x,to.z});
            //cout<<to.x<<" "<<to.y<<" "<<to.z<<endl;
        }
    }

    /*
    DEBUG
    */
    for(int i=1;i<=n;i++)
        if(dis[i]!=0)dis[i]=2e9;
        else q.push({0,i});
    while(!q.empty()){
        int v=q.top().second;
        int val=-q.top().first;
        q.pop();
        if(val>dis[v])continue;
        for(auto to:g[v]){
            if(dis[to.first]>val+to.second){
                dis[to.first]=val+to.second;
                q.push({-dis[to.first],to.first});
            }
        }
    }
    /*
    DEBUG
    */


    //dfs(1,1,2e9);
    scanf("%d",&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        int l=lca(x,y);
        //printf("%d\n",min(go(x,l),go(y,l)));
        cout<<min(dis[x],dis[y])<<'\n';
    }
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:130:13: warning: unused variable 'l' [-Wunused-variable]
  130 |         int l=lca(x,y);
      |             ^
plan.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
plan.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         scanf("%d%d%d",&e.x,&e.y,&e.z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
plan.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~
plan.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
plan.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  129 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...