Submission #981780

#	Time	Username	Problem	Language	Result	Execution time	Memory
981780		kaopj	Evacuation plan (IZhO18_plan)	C++14	100 / 100	834 ms	84704 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(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(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:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         auto [u , w] = pq.top();
      |              ^
plan.cpp:58:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         for(auto [v , ww] : adj[u]){
      |                  ^
plan.cpp: In function 'void dfs(int, int)':
plan.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for(auto [v , w] : tree[u]){
      |              ^
plan.cpp: In function 'int main()':
plan.cpp:138:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |     for(auto [u,v,w] : edge_input){
      |              ^
plan.cpp:144:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  144 |     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