제출 #42556

#제출 시각아이디문제언어결과실행 시간메모리
42556wzyEvacuation plan (IZhO18_plan)C++11
100 / 100
813 ms88920 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define int long long #define S second #define mp make_pair #define pb push_back #define pii pair<int,int> int n , m , k , d[100005] , pai[100005] , peso[100005] , fn[100005] , sparse[100005][22] , custo[100005] , anc[100005][22] , h[100005]; vector<pii> adj[100005]; struct edges{ int x , y, z; }; bool cmp(edges a , edges b){ return a.z > b.z; } void pre(int i , int j){ if(i == j) h[i] = 0; for(int y = 0 ; y < adj[i].size();y++){ pii v = adj[i][y]; if(v.S == j) continue; fn[v.S] = i; custo[v.S] = v.F; h[v.S] = h[i] + 1; pre(v.S , i); } } int fd(int x){ return pai[x] == x ? x : pai[x] = fd(pai[x]);} void join(int u , int v){ u = fd(u) , v = fd(v); if(peso[u] > peso[v]) swap(u,v); pai[u] = v, peso[v] += peso[u] + 1; } int query(int x , int y){ if(h[x] < h[y]) swap(x,y); int ansj = (int) 1e18; for(int i = 21 ; i >= 0 ; i--){ if(h[x] >= h[y] + (1LL<<i)){ ansj = min(ansj , sparse[x][i]); x = anc[x][i]; } } if(x == y) return ansj; for(int i = 21 ; i >= 0 ; i--){ if(anc[x][i] != anc[y][i] && anc[x][i] != -1){ ansj = min(ansj , sparse[x][i]); ansj = min(ansj , sparse[y][i]); x = anc[x][i] , y = anc[y][i]; } } ansj = min(ansj , sparse[x][0]); ansj = min(ansj , sparse[y][0]); return ansj; } int32_t main(){ scanf("%lld%lld" , &n, &m); vector<edges> v; for(int i = 0 ; i <n;i++){ pai[i] = i , peso[i] = 0 , d[i] = (int) 1e18; } for(int i = 0 ; i < m ; i++){ int x,y,z; scanf("%lld%lld%lld" , &x , &y , &z); x--, y--; v.pb({x,y,z}); adj[x].pb(pii(z,y)); adj[y].pb(pii(z,x)); } scanf("%lld" , &k); priority_queue<pii , vector<pii> , greater<pii> > pq; for(int i = 0 ; i < k ; i++) { int x; scanf("%lld" , &x); x--; d[x] = 0; pq.push(pii(0,x)); } while(!pq.empty()){ pii u = pq.top(); pq.pop(); if(d[u.S] != u.F) continue; for(int j = 0 ; j < adj[u.S].size();j++){ pii v = adj[u.S][j]; if(d[v.S] > v.F + u.F){ d[v.S] = v.F + u.F; pq.push(pii(d[v.S] , v.S)); } } } for(int i = 0 ; i < m ; i++){ v[i].z = min(d[v[i].x] , d[v[i].y]); adj[v[i].x].clear(); adj[v[i].y].clear(); } sort(v.begin() , v.end() , cmp); for(int i = 0 ; i <m;i++){ if(fd(v[i].x) != fd(v[i].y)){ join(v[i].x , v[i].y); adj[v[i].x].pb(pii(v[i].z , v[i].y)); adj[v[i].y].pb(pii(v[i].z , v[i].x)); } } for(int i=0;i<100005;i++) custo[i] = (int) 1e18; for(int i = 0 ; i < 100005 ; i++) for(int j = 0 ; j < 22 ; j++) anc[i][j] = -1 , sparse[i][j] = (int) 1e18; memset(fn , -1 , sizeof fn); pre(0 , 0); for(int i = 0 ; i < 100005 ; i++){ if(fn[i] != -1) anc[i][0] = fn[i] , sparse[i][0] = custo[i]; } for(int j = 1; j < 22 ; j++){ for(int i = 0 ; i < 100005;i++){ if(anc[i][j-1] != -1) anc[i][j] = anc[anc[i][j-1]][j-1] , sparse[i][j] = min(sparse[i][j-1] , sparse[anc[i][j-1]][j-1]); } } int q; scanf("%lld" , &q); while(q--){ int x,y; scanf("%lld%lld" , &x , &y); x-- ,y--; printf("%lld\n" , query(x,y)); } }

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'void pre(long long int, long long int)':
plan.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int y = 0 ; y < adj[i].size();y++){
                  ~~^~~~~~~~~~~~~~~
plan.cpp: In function 'int32_t main()':
plan.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < adj[u.S].size();j++){
                   ~~^~~~~~~~~~~~~~~~~
plan.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld" , &n,  &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld" , &x , &y , &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &k);
  ~~~~~^~~~~~~~~~~~~
plan.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld" , &x);
   ~~~~~^~~~~~~~~~~~~
plan.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &q);
  ~~~~~^~~~~~~~~~~~~
plan.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld" , &x , &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...