Submission #979604

#	Time	Username	Problem	Language	Result	Execution time	Memory
979604		SeenSiravit	Evacuation plan (IZhO18_plan)	C++14	100 / 100	821 ms	84948 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;

struct EDGE {
    int u,v;
    ll w;

    bool operator < (const EDGE &d2) const{
        return w > d2.w;
    }
};

struct ADJ {
    int u;
    ll w;

    bool operator < (const ADJ &d2) const{
        return w > d2.w;
    }
};


int n,m,n_npp;
vector<ADJ> adj[mxN];
vector<EDGE> edge_input;
vector<EDGE> edge_new;
vector<ADJ> tree[mxN];
bool npp[mxN];
ll dis[mxN];
int cmp[mxN];
int depth[mxN];
ll dp[mxN][mxLogDepth];
int ancestor[mxN][mxLogDepth];

void dijkstra_npp(){
    for(int i=1;i<=n;i++) dis[i] = LLONG_MAX;

    priority_queue<ADJ> pq;

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

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

        if(dis[u] < w) continue;

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

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

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 lca(int u, int v){
    if(depth[u] > depth[v]) swap(u , v);

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

    for(int k=0;k<=limDepth;k++){
        if((1<<k) & diff){
            ans = min(ans , dp[v][k]);
            v = ancestor[v][k];
        }
    }

    if(u == v){
        cout<< ans << '\n';
        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 = ancestor[u][k];
            v = ancestor[v][k];
        }
    }

    ans = min({ans , dp[u][0] , dp[v][0]});
    cout<< ans << '\n';
}

int main(){
    cin>> n >> m;

    for(int i=0;i<m;i++){
        int u,v;
        ll w;
        cin>> u >> v >> w;
        
        adj[u].push_back({v , w});
        adj[v].push_back({u , w});

        edge_input.push_back({u , v , w});
    }

    int n_npp;
    cin>> n_npp;

    for(int i=1;i<=n;i++) npp[i] = false;
    for(int i=0;i<n_npp;i++){
        int node;
        cin>> node;
        npp[node] = true;
    }

    dijkstra_npp();
    // for(int i=1;i<=n;i++) cout<< dis[i] <<  " ";
    // cout<< "\n";

    for(auto [u,v,w] : edge_input){
        edge_new.push_back({u , v , min(dis[u] , dis[v])});
    }

    sort(edge_new.begin() , edge_new.end());

    // for(auto [u,v,w] : edge_new) cout<< u << " " << v << " " << w << "\n";

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

    for(auto [u,v,w] : edge_new){
        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});
        cmp[pa_v] = pa_u;
    }

    for(int i=0;i<mxN;i++){
        for(int j=0;j<mxLogDepth;j++){
            dp[i][j] = LLONG_MAX;
            ancestor[i][j] = 0;
        }
    }

    dfs(1 , -1);

    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]);
        }
    }

    int q;
    cin>> q;

    while(q--){
        int u,v;
        cin>> u >> v;
        lca(u , v);
    }
}

Compilation message (stderr)

plan.cpp: In function 'void dijkstra_npp()':
plan.cpp:54:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         auto [u , w] = pq.top();
      |              ^
plan.cpp:59:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for(auto [v , ww] : adj[u]){
      |                  ^
plan.cpp: In function 'void dfs(int, int)':
plan.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for(auto [v , w] : tree[u]){
      |              ^
plan.cpp: In function 'int main()':
plan.cpp:143:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  143 |     for(auto [u,v,w] : edge_input){
      |              ^
plan.cpp:153:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |     for(auto [u,v,w] : edge_new){
      |              ^

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