제출 #979548

#제출 시각아이디문제언어결과실행 시간메모리
979548SeenSiravitEvacuation plan (IZhO18_plan)C++14
0 / 100
216 ms42548 KiB
#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){ 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; }

컴파일 시 표준 에러 (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 '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);
      |         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...