제출 #217702

#제출 시각아이디문제언어결과실행 시간메모리
217702FischerValley (BOI19_valley)C++14
23 / 100
212 ms37860 KiB
#include <bits/stdc++.h> #define re(x, y, z) for (int x=y; x<z; ++x) #define trav(v, x) for (int v : x) #define eb emplace_back using namespace std; const int maxn = 1e5 + 10; long long h[maxn]; int lo[maxn], hi[maxn]; long long dist[maxn]; long long down[maxn]; using ii = pair<int, int>; vector<ii> g[maxn]; int n, s, q, e; ii edges[maxn]; int id[maxn]; bool shop[maxn]; const int LOG = 18; int up[maxn][LOG]; long long st[maxn][LOG]; using lli = pair<long long, int>; priority_queue<lli, vector<lli>, greater<lli>> Q; const long long inf = 1e18; int T = 0; long long dfs(int x, int p, long long he) { h[x] = he; lo[x] = T++; down[x] = shop[x] ? 0 : inf; for (auto node : g[x]) { if (node.first == p) continue; dfs(node.first, x, he + node.second); down[x] = min(down[x], down[node.first] + node.second); } st[x][0] = down[x] - h[x]; up[x][0] = p==-1 ? x : p; for (int k = 1; k < LOG; ++k) { st[x][k] = min(st[x][k-1], st[up[x][k-1]][k-1]); up[x][k] = up[up[x][k-1]][k-1]; } hi[x] = T++; } bool isParent(int x, int y) { return lo[x] <= lo[y] and hi[y] <= hi[x]; } void dikjstra() { while (!Q.empty()) { auto q = Q.top(); Q.pop(); if (q.first != dist[q.second]) continue; for (auto node : g[q.second]) { if (q.first + node.second < dist[node.first]) { dist[node.first] = q.first + node.second; id[node.first] = id[q.second]; Q.push({dist[node.first], node.first}); } } } } long long query(int x, int y) { int len = h[x] - h[y] + 1; long long ans = inf; for (int k = 0; k < LOG; ++k) { if (len & (1<<k)) { ans = min(ans, st[x][k]); x = up[x][k]; } } return ans; } int main() { scanf("%d%d%d%d", &n, &s, &q, &e); re(i, 1, n) { int a, b, w; scanf("%d%d%d", &a, &b, &w); g[a].eb(b, w); g[b].eb(a, w); edges[i] = {a, b}; } re(i, 1, n+1) dist[i] = inf; re(i, 0, s) { int c; scanf("%d", &c); id[c] = c; dist[c] = 0; shop[c] = 1; Q.push({0, c}); } dfs(e, 0, 0); dikjstra(); re(i, 0, q) { int I, R; scanf("%d%d", &I, &R); int a = edges[I].first, b = edges[I].second; if (h[a] > h[b]) swap(a, b); if (isParent(b, R)) { if (down[b] == inf) puts("oo"); else { if (isParent(b, id[R])) { printf("%lld\n", dist[R]); } else { printf("%lld\n", query(R, b) + h[R]); } } } else puts("escaped"); } return 0; }

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

valley.cpp: In function 'long long int dfs(int, int, long long int)':
valley.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
valley.cpp: In function 'int main()':
valley.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &n, &s, &q, &e);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c);
   ~~~~~^~~~~~~~~~
valley.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &I, &R);
   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...