제출 #1094317

#제출 시각아이디문제언어결과실행 시간메모리
1094317anha3k25cvpValley (BOI19_valley)C++17
23 / 100
85 ms26316 KiB
#include <bits/stdc++.h> #define ll long long #define dl double #define st first #define nd second #define II pair <int, int> using namespace std; const int N = 5 + 1e5; const ll inf = 7 + 1e18; struct Edge { int u, v, w; }; int node = 0, logn; vector <int> in, ou, h; vector <ll> f; vector <Edge> e; vector <vector <int>> adj, p; void dfs(int u) { in[u] = ++ node; for (int i : adj[u]) { int v = e[i].u + e[i].v - u; if (!in[v]) { h[v] = h[u] + 1; p[0][v] = u; f[v] = f[u] + e[i].w; dfs(v); } } ou[u] = node; } int lca(int u, int v) { if (h[u] < h[v]) swap(u, v); for (int si = h[u] - h[v]; si > 0; si ^= si & -si) { int i = __builtin_ctz(si & -si); u = p[i][u]; } if (u == v) return u; for (int i = logn - 1; i >= 0; i --) if (p[i][u] != p[i][v]) { u = p[i][u]; v = p[i][v]; } return p[0][u]; } ll dis(int u, int v) { return f[u] + f[v] - f[lca(u, v)] * 2; } vector <int> siz, pre; void dfs(int u, int par) { siz[u] = 1; for (int i : adj[u]) { int v = e[i].u + e[i].v - u; if (v != par && pre[v] < 0) { dfs(v, u); siz[u] += siz[v]; } } } int centroid(int u, int par) { for (int i : adj[u]) { int v = e[i].u + e[i].v - u; if (pre[v] < 0 && v != par && siz[v] * 2 > siz[u]) return centroid(v, u); } return u; } void build(int u, int par) { dfs(u, par); int c = centroid(u, par); pre[c] = par; for (int i : adj[c]) { int v = e[i].u + e[i].v - c; if (pre[v] < 0) build(v, c); } } vector <int> lg; bool cmp(int u, int v) { return in[u] < in[v]; } struct Tree { vector <ll> a; vector <vector <ll>> mi; void build(int root) { int n = a.size(); sort(a.begin(), a.end(), cmp); mi.assign(logn, vector <ll> (n, 0)); for (int i = 0; i < n; i ++) mi[0][i] = dis(a[i], root); for (int i = 1; i < logn; i ++) for (int u = 0; u < n; u ++) if (u + (1 << i) - 1 < n) mi[i][u] = min(mi[i - 1][u], mi[i - 1][u + (1 << (i - 1))]); } ll get_min(int l, int r) { if (l > r) return inf; int bit = lg[r - l + 1]; return min(mi[bit][l], mi[bit][r - (1 << bit) + 1]); } ll get_ans(int l, int r, int type) { if (a.empty()) return inf; int n = a.size(), lo = 0, hi = n - 1; while (lo < hi) { int mid = (lo + hi) / 2; if (in[a[mid]] >= l) hi = mid; else lo = mid + 1; } if (type) { if (l <= in[a[lo]] && in[a[lo]] <= r) { int L = lo; hi = n - 1; while (lo < hi) { int mid = (lo + hi + 1) / 2; if (in[a[mid]] <= r) lo = mid; else hi = mid - 1; } return get_min(L, lo); } return inf; } if (l <= in[a[lo]] && in[a[lo]] <= r) { int L = lo; hi = n - 1; while (lo < hi) { int mid = (lo + hi + 1) / 2; if (in[a[mid]] <= r) lo = mid; else hi = mid - 1; } return min(get_min(1, L - 1), get_min(lo + 1, n - 1)); } return get_min(0, n - 1); } }; vector <Tree> T; void update(int u) { int v = u; while (v > 0) { T[v].a.push_back(u); v = pre[v]; } } int main() { #define TASKNAME "" ios_base :: sync_with_stdio (0); cin.tie (0); if ( fopen( TASKNAME".inp", "r" ) ) { freopen( TASKNAME".inp", "r", stdin ); freopen( TASKNAME".out", "w", stdout ); } int n, s, q, root; cin >> n >> s >> q >> root; e.resize(n); adj.resize(n + 1); for (int i = 1; i < n; i ++) { cin >> e[i].u >> e[i].v >> e[i].w; adj[e[i].u].push_back(i); adj[e[i].v].push_back(i); } vector <int> a(n + 1, 0); for (int i = 1; i <= s; i ++) { int u; cin >> u; a[u] = 1; } for (logn = 1; (1 << logn) <= n; logn ++); p.assign(logn, vector <int> (n + 1, 0)); in.assign(n + 1, 0); ou.assign(n + 1, 0); h.assign(n + 1, 0); f.assign(n + 1, 0); h[1] = 1; dfs(1); for (int i = 1; i < logn; i ++) for (int u = 1; u <= n; u ++) p[i][u] = p[i - 1][p[i - 1][u]]; for (int i = 1; i < n; i ++) if (in[e[i].u] > in[e[i].v]) swap(e[i].u, e[i].v); if (s == n) { while (q --) { int id, u; cin >> id >> u; int l = in[e[id].v], r = ou[e[id].v], check = (l <= in[u] && in[u] <= r), v = u, check1 = (l <= in[root] && in[root] <= r); if (check == check1) { cout << "escaped\n"; continue; } cout << "0\n"; } return 0; } siz.assign(n + 1, 0); pre.assign(n + 1, -1); build(1, 0); lg.assign(n + 1, 0); for (int i = 2; i <= n; i ++) lg[i] = lg[i >> 1] + 1; T.resize(n + 1); for (int i = 1; i <= n; i ++) if (a[i]) update(i); for (int i = 1; i <= n; i ++) T[i].build(i); while (q --) { int id, u; cin >> id >> u; int l = in[e[id].v], r = ou[e[id].v], check = (l <= in[u] && in[u] <= r), v = u, check1 = (l <= in[root] && in[root] <= r); if (check == check1) { cout << "escaped\n"; continue; } if (a[u]) { cout << "0\n"; continue; } ll mi = inf; while (v > 0) { ll val = T[v].get_ans(l, r, check); if (val < inf) mi = min(mi, dis(u, v) + val); v = pre[v]; } if (mi < inf) cout << mi << '\n'; else cout << "oo\n"; } return 0; }

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

valley.cpp: In function 'int main()':
valley.cpp:210:87: warning: unused variable 'v' [-Wunused-variable]
  210 |             int l = in[e[id].v], r = ou[e[id].v], check = (l <= in[u] && in[u] <= r), v = u,
      |                                                                                       ^
valley.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         freopen( TASKNAME".inp", "r", stdin );
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen( TASKNAME".out", "w", stdout );
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...