제출 #130958

#제출 시각아이디문제언어결과실행 시간메모리
130958IOrtroiiiValley (BOI19_valley)C++14
23 / 100
314 ms35924 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll inf = 1e18; const int N = 100100; int n, m, q, root; int from[N], to[N]; vector<pair<int, int>> g[N]; ll dep[N], down[N]; int par[17][N]; ll minPar[17][N]; int tin[N], tout[N], tt; void dfs(int u) { for (int i = 1; i < 17; ++i) { par[i][u] = par[i - 1][par[i - 1][u]]; } tin[u] = ++tt; for (auto e : g[u]) { int v, w; tie(v, w) = e; if (v != par[0][u]) { par[0][v] = u; dep[v] = dep[u] + w; dfs(v); } } tout[u] = tt; } bool isAnc(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; } void dfsDown(int u) { for (auto e : g[u]) { int v, w; tie(v, w) = e; if (v != par[0][u]) { dfsDown(v); down[u] = min(down[u], down[v] + w); } } minPar[0][u] = down[u] - dep[u]; } void debug(ll a[], string s) { cout << s << "\n"; for (int i = 1; i <= n; ++i) { printf("%lld ", a[i]); } puts(""); } int main() { scanf("%d %d %d %d", &n, &m, &q, &root); for (int i = 1; i < n; ++i) { int cost; scanf("%d %d %d", from + i, to + i, &cost); g[from[i]].emplace_back(to[i], cost); g[to[i]].emplace_back(from[i], cost); } par[0][root] = root; dfs(root); for (int i = 1; i <= n; ++i) { down[i] = inf; } while (m--) { int v; scanf("%d", &v); down[v] = 0; } dfsDown(root); for (int i = 1; i < 17; ++i) { for (int u = 1; u <= n; ++u) { minPar[i][u] = min(minPar[i - 1][u], minPar[i - 1][par[i - 1][u]]); } } for (int i = 1; i < n; ++i) { if (dep[from[i]] > dep[to[i]]) { swap(from[i], to[i]); } } while (q--) { int id, v; scanf("%d %d", &id, &v); if (!isAnc(to[id], v)) { puts("escaped"); continue; } ll ans = inf; int u = v; for (int i = 16; i >= 0; --i) { if (dep[par[i][u]] >= dep[from[id]]) { ans = min(ans, minPar[i][u]); u = par[i][u]; } } if (ans > (inf / 10)) { puts("oo"); } else { printf("%lld\n", ans + dep[v]); } } }

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

valley.cpp: In function 'int main()':
valley.cpp:59:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d %d", &n, &m, &q, &root);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:62:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d", from + i, to + i, &cost);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:73:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &v);
       ~~~~~^~~~~~~~~~
valley.cpp:89:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &id, &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...