Submission #979540

#	Time	Username	Problem	Language	Result	Execution time	Memory
979540		SeenSiravit	Evacuation plan (IZhO18_plan)	C++14	0 / 100	195 ms	42620 KiB

plan

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define pill pair<int,ll>

using namespace std;

const int mxN = 1e5 + 5 , mxLogDepth = 20 , limDepth=17;

int n,m,n_npp;
vector<pii> g[mxN];
vector<pii> adj;
bool npp[mxN];

// dijkstra npp
ll dis[mxN];

// build new graph
struct EDGE
{
    int u,v;
    ll w;
    bool operator < (const EDGE &edge2) const{
        return w < edge2.w;
    }
};
vector<pill> tree[mxN];
int dsu[mxN];

// lca
int depth[mxN];
int ancestor[mxN][mxLogDepth];
ll dp[mxN][mxLogDepth];

void dijkstra_npp(){
    for(int i=0;i<mxN;i++) dis[i] = INT_MAX;

    priority_queue<pill ,  vector<pill> , greater<pill>> pq;

    for(int i=1;i<=n;i++){
        if(npp[i]){
            dis[i] = 0;
            pq.push({dis[i] , i});
        }
    }

    while(!pq.empty()){
        auto [w , u] = pq.top();
        pq.pop();

        if(dis[u] < w) continue;

        for(auto [v , ww] : g[u]){
            if(dis[v] > w + ww){
                dis[v] = w + ww;
                pq.push({dis[v] , v});
            }
        }
    }
}

int fp(int x){
    if(dsu[x] == x) return x;
    return dsu[x] = fp(dsu[x]);
}

void build_newGraph(){
    priority_queue<EDGE> pq;

    for(auto [u , v] : adj){
        pq.push({u , v , min(dis[u] , dis[v])});
    }

    for(int i=1;i<=n;i++) dsu[i] = i;

    while(!pq.empty()){
        auto [u,v,w] = pq.top();
        pq.pop();

        int pa_u = fp(u) , pa_v = fp(v);

        if(pa_u == pa_v) continue;

        tree[u].push_back({v , w});
        tree[v].push_back({u , w});
        dsu[pa_v] = pa_u;

        // printf("%d %d %d\n",u,v,w);
    }
}

void dfs(int u , int pa){
    for(auto [v , w] : tree[u]){
        if(v == pa) continue;

        depth[v] = depth[u] + 1;
        ancestor[v][0] = u;
        dp[v][0] = w;

        dfs(v , u);
    }
}

void k_ancestor(){
    for(int k=1;k<=limDepth;k++){
        for(int node=1;node<=n;node++){
            ancestor[node][k] = ancestor[ancestor[node][k-1]][k-1];
            dp[node][k] = min(dp[node][k-1] , dp[ancestor[node][k-1]][k-1]);
        }
    }
}

void pre_LCA(){
    for(int i=0;i<mxN;i++) depth[i]=-1 , ancestor[i][0] = 0;

    depth[1] = 1;

    dfs(1 , -1);

    // for(int i=1;i<=n;i++) printf("%d ",depth[i]);
    // printf("\n");

    k_ancestor();

    // printf("\n");
    // for(int k=0;k<4;k++) printf("%d %d\n" , ancestor[2][k] , dp[2][k]);
}

void LCA(int u , int v){
    if(depth[u] > depth[v]){
        LCA(v , u);
        return ;
    }

    // printf("start (%d , %d) | (%d , %d)\n",u,depth[u],v,depth[v]);

    int diff = depth[v] - depth[u];
    ll ans = min(dis[u] , dis[v]);

    for(int i=0;i<=limDepth;i++){
        if((1<<i) & diff){
            ans = min(ans , dp[v][i]);
            v = ancestor[v][i];
        }
    }
    
    // printf("after lift v : (%d %d) (%d %d)\n",u,depth[u],v,depth[v]);

    if(u == v){
        printf("%d\n",ans);
        return ;
    }

    for(int k=limDepth;k>=0;k--){
        if(ancestor[u][k] == ancestor[v][k]){
            ans = min({ans , dp[u][k] , dp[v][k]});
            u = dp[u][k];
            v = dp[v][k];
        }
    }

    ans = min({ans , dp[u][0] , dp[v][0]});

    printf("%d\n",ans);
}

int main(){

    scanf("%d %d" ,&n ,&m);

    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        adj.push_back({u,v});
    }

    scanf("%d",&n_npp);

    for(int i=0;i<mxN;i++) npp[i] = false;
    for(int i=0;i<n_npp;i++){
        int node;
        scanf("%d",&node);
        npp[node] = true;
    }

    dijkstra_npp();

    // printf("dis : ");
    // for(int i=1;i<=n;i++) printf("%d ",dis[i]);
    // printf("\n\n");

    build_newGraph();

    pre_LCA();

    int q;
    scanf("%d",&q);

    while(q--){
        int u,v;
        scanf("%d %d",&u,&v);
        LCA(u,v);
    }

    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void dijkstra_npp()':
plan.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         auto [w , u] = pq.top();
      |              ^
plan.cpp:53:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         for(auto [v , ww] : g[u]){
      |                  ^
plan.cpp: In function 'void build_newGraph()':
plan.cpp:70:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for(auto [u , v] : adj){
      |              ^
plan.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |         auto [u,v,w] = pq.top();
      |              ^
plan.cpp: In function 'void dfs(int, int)':
plan.cpp:93:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |     for(auto [v , w] : tree[u]){
      |              ^
plan.cpp: In function 'void LCA(int, int)':
plan.cpp:150:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  150 |         printf("%d\n",ans);
      |                 ~^    ~~~
      |                  |    |
      |                  int  long long int
      |                 %lld
plan.cpp:164:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  164 |     printf("%d\n",ans);
      |             ~^    ~~~
      |              |    |
      |              int  long long int
      |             %lld
plan.cpp: In function 'int main()':
plan.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |     scanf("%d %d" ,&n ,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:173:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         scanf("%d %d %d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |     scanf("%d",&n_npp);
      |     ~~~~~^~~~~~~~~~~~~
plan.cpp:184:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |         scanf("%d",&node);
      |         ~~~~~^~~~~~~~~~~~
plan.cpp:199:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
plan.cpp:203:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

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