Submission #979572

# Submission time Handle Problem Language Result Execution time Memory
979572 2024-05-11T07:53:21 Z SeenSiravit Evacuation plan (IZhO18_plan) C++14
0 / 100
207 ms 42616 KB
#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;
 
    ancestor[1][0] = 1;
    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){
        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 = dp[u][k];
            v = dp[v][k];
        }
    }
 
    ans = min({ans , dp[u][0] , dp[v][0]});
 
    cout<< ans << "\n";
}
 
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

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 'int main()':
plan.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     scanf("%d %d" ,&n ,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:174:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         scanf("%d %d %d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |     scanf("%d",&n_npp);
      |     ~~~~~^~~~~~~~~~~~~
plan.cpp:185:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         scanf("%d",&node);
      |         ~~~~~^~~~~~~~~~~~
plan.cpp:200:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
plan.cpp:204:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 15708 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 207 ms 42616 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -