제출 #168796

#제출 시각아이디문제언어결과실행 시간메모리
168796abilEvacuation plan (IZhO18_plan)C++14
0 / 100
474 ms42376 KiB
#include <bits/stdc++.h> #define fr first #define sc second #define pb push_back #define mk make_pair #define all(s) s.begin(),s.end() //#define int long long using namespace std; const int N = (2e5 + 12); const int mod = (1e9 + 7); const int INF = (0x3f3f3f3f); vector<pair<int,int > > g[N], gg[N]; vector<pair<int,int > > vec; int dist[N], par[N], sz[N], up[22][N], mn[22][N], tin[N], tout[N], timer, was[N]; int find(int v){ if(v == par[v]){ return v; } return par[v] = find(par[v]); } void dsu(int a,int b){ a = find(a); b = find(b); if(sz[a] < sz[b]){ swap(a, b); } sz[a] += sz[b]; par[b] = a; } void dfs(int v,int pr,int w){ up[0][v] = pr; mn[0][v] = w; tin[v] = ++timer; for(int i = 1;i <= 19; i++){ up[i][v] = up[i - 1][up[i - 1][v]]; mn[i][v] = min(mn[i - 1][v], mn[i - 1][up[i - 1][v]]); } for(auto to : g[v]){ if(to.fr != pr){ dfs(to.fr, v, to.sc); } } tout[v] = ++timer; } bool upper(int a,int b){ return tin[a] <= tin[b] && tout[a] >= tout[b]; } int get(int a,int b){ int res = INF; if(upper(a, b)){ for(int i = 19;i >= 0; i--){ if(!upper(up[i][b], a)){ res = min(res, mn[i][b]); b = up[i][b]; } } res = min(res, mn[0][b]); } else if(upper(b, a)){ for(int i = 19;i >= 0; i--){ if(!upper(up[i][b], a)){ res = min(res, mn[i][a]); a = up[i][a]; } } res = min(res, mn[0][a]); } else{ for(int i = 19;i >= 0; i--){ if(!upper(up[i][b], a)){ res = min(res, mn[i][b]); b = up[i][b]; } } res = min(res, mn[0][b]); for(int i = 19;i >= 0; i--){ if(!upper(up[i][b], a)){ res = min(res, mn[i][a]); a = up[i][a]; } } res = min(res, mn[0][a]); } return res; } main() { int n, m, u, v, w; scanf("%d%d", &n, &m); for(int i = 1;i <= n; i++){ par[i] = i; sz[i] = 1; } for(int i = 1;i <= m; i++){ scanf("%d%d%d", &u, &v, &w); g[u].pb({v,w}); g[v].pb({u,w}); gg[u].pb({v,w}); gg[v].pb({u,w}); } int k; priority_queue<pair<int,int > > q; scanf("%d", &k); memset(dist, 0x3f3f3f3f,sizeof(dist)); for(int i = 0;i < k; i++){ scanf("%d", &v); dist[v] = 0; q.push({0,v}); } while(!q.empty()){ v = q.top().sc; w = -q.top().fr; q.pop(); if(w > dist[v]){ continue; } for(auto to : g[v]){ if(dist[to.fr] > dist[v] + to.sc){ dist[to.fr] = dist[v] + to.sc; q.push({-dist[to.fr], to.fr}); } } } for(int i = 1;i <= n; i++){ g[i].clear(); vec.pb({dist[i], i}); } sort(all(vec)); reverse(all(vec)); for(int i = 0;i < n; i++){ v = vec[i].sc, w = vec[i].fr; was[v] = 1; for(auto to : gg[v]){ if(!was[to.fr]){ continue; } u = to.fr; if(find(v) != find(u)){ g[v].pb({u, min(w,dist[u])}); g[u].pb({v, min(w,dist[u])}); dsu(u,v); } } } dfs(vec[n - 1].sc, vec[n - 1].sc, INF); int t; scanf("%d", &t); while(t--){ scanf("%d%d", &u, &v); printf("%d\n", get(u, v)); } } /* 9 12 1 9 4 1 2 5 2 3 7 2 4 3 4 3 6 3 6 4 8 7 10 6 7 5 5 8 1 9 5 7 5 4 12 6 8 2 2 4 7 5 1 6 5 3 4 8 5 8 1 5 */

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

plan.cpp:97:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
plan.cpp: In function 'int main()':
plan.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
plan.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v);
   ~~~~~^~~~~~~~~~
plan.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
  ~~~~~^~~~~~~~~~
plan.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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...