Submission #170771

#	Time	Username	Problem	Language	Result	Execution time	Memory
170771		juggernaut	Evacuation plan (IZhO18_plan)	C++14	0 / 100	358 ms	60764 KiB

plan

//Just try and the idea will come!
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int n,m,x,y,z,v,dis[100001],i,par[100001],sz[100001],tin[100001],tout[100001],timer,up[100001][20],mn[100001][20];
vector<pair<int,int>>p;
vector<vector<pair<int,int>>>g(100001);
vector<pair<int,pair<int,int>>>vec;
int fin(int v){
    if(v==par[v])return v;
    return par[v]=fin(par[v]);
}
void dfs(int v,int p,int cost){
    tin[v]=timer++;
    up[v][0]=p;
    mn[v][0]=cost;
    for(int i=1;i<20;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];
}
int lca(int a,int b){
    if(upper(a,b))return a;
    if(upper(b,a))return b;
    for(int i=19;i>=0;i--)if(!upper(up[a][i],b))a=up[a][i];
    return up[a][0];
}
int get(int a,int b){
    int l=lca(a,b);
    int res=min(dis[a],dis[b]);
    if(!upper(l,a))
    for(int i=19;i>=0;i--){
        if(!upper(up[a][i],l)){
            res=min(res,mn[a][i]);
            a=up[a][i];
        }
    }
    if(!upper(l,b))
    for(int i=19;i>=0;i--){
        if(!upper(up[b][i],l)){
            res=min(res,mn[b][i]);
            b=up[b][i];
        }
    }
    return res;
}
main(){
    scanf("%lld%lld",&n,&m);
    while(m--){
        scanf("%lld%lld%lld",&x,&y,&z);
        g[x].push_back({y,z});
        g[y].push_back({x,z});
        p.push_back({x,y});
    }
    for(i=1;i<=n;i++)dis[i]=1e15,par[i]=i,sz[i]=1;
    scanf("%lld",&m);
    priority_queue<pair<int,int>>q;
    while(m--){
        scanf("%lld",&x);
        dis[x]=0;
        q.push({0,x});
    }
    while(!q.empty()){
        v=q.top().second;
        q.pop();
        for(auto to:g[v])
            if(dis[to.first]>dis[v]+to.second){
                dis[to.first]=dis[v]+to.second;
                q.push({-dis[to.first],to.first});
            }
    }
    for(i=0;i<p.size();i++)vec.push_back({min(dis[p[i].first],dis[p[i].second]),{p[i].first,p[i].second}});
    for(i=1;i<=n;i++)g[i].clear();
    sort(vec.rbegin(),vec.rend());
    for(i=0;i<vec.size();i++){
        x=fin(vec[i].second.first);
        y=fin(vec[i].second.second);
        if(x!=y){
            if(sz[x]<sz[y])swap(x,y);
            par[y]=x;
            sz[x]+=sz[y];
            g[vec[i].second.first].push_back({vec[i].second.second,vec[i].first});
            g[vec[i].second.second].push_back({vec[i].second.first,vec[i].first});
        }
    }
    dfs(1,0,1e15);
    scanf("%lld",&m);
    while(m--){
        scanf("%lld%lld",&x,&y);
        printf("query:%lld\n",get(x,y));
    }
}

Compilation message (stderr)

plan.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
plan.cpp: In function 'int main()':
plan.cpp:77:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<p.size();i++)vec.push_back({min(dis[p[i].first],dis[p[i].second]),{p[i].first,p[i].second}});
             ~^~~~~~~~~
plan.cpp:80:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<vec.size();i++){
             ~^~~~~~~~~~~
plan.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~
plan.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&x,&y,&z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&m);
     ~~~~~^~~~~~~~~~~
plan.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&x);
         ~~~~~^~~~~~~~~~~
plan.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&m);
     ~~~~~^~~~~~~~~~~
plan.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~~~~

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