제출 #1082393

#제출 시각아이디문제언어결과실행 시간메모리
1082393vuavisaoValley (BOI19_valley)C++14
59 / 100
78 ms24148 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; using ll = long long; const int N = 100'000 + 10; const ll INF = 1'000'000'000'000'000'000; int n, numStores, q, escape; tuple<int, int, int> edges[N]; int positionStore[N]; namespace sub12 { bool check() { return (1ll * n * q <= 10'000'000); } vector<vector<pair<int, int>>> g; ll dist[N]; void solve() { g.resize(n + 1); while (q -- > 0) { for (int u = 1; u <= n; ++ u) { g[u].clear(); dist[u] = INF; } int path, curPosition; cin >> path >> curPosition; for (int i = 1; i <= n - 1; ++ i) { if (i == path) continue; int u = get<0>(edges[i]), v = get<1>(edges[i]), w = get<2>(edges[i]); g[u].push_back(make_pair(v, w)); g[v].push_back(make_pair(u, w)); } queue<int> q; q.push(curPosition); dist[curPosition] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (const auto& x : g[u]) { int v = x.first, w = x.second; if (dist[v] < INF) continue; dist[v] = dist[u] + w; q.push(v); } } if (dist[escape] < INF) { cout << "escaped"; } else { ll res = INF; for (int i = 1; i <= numStores; ++ i) { res = min(res, dist[positionStore[i]]); } if (res >= INF) { cout << "oo"; } else { cout << res; } } cout << '\n'; } } } namespace sub3 { bool check() { return (numStores == n); } vector<vector<int>> g; int Lg, dist[N], parent[20][N]; int cnt, in[N], out[N]; void dfs(int u, int p) { in[u] = ++ cnt; for (const auto& v : g[u]) { if (v == p) continue; parent[0][v] = u; dist[v] = dist[u] + 1; dfs(v, u); } out[u] = cnt; }; int lca(int u, int v) { if (dist[u] < dist[v]) swap(u, v); int delta = dist[u] - dist[v]; for (int lg = Lg; lg >= 0; -- lg) { if (((delta >> lg) & 1)) { u = parent[lg][u]; } } if (u == v) return u; for (int lg = Lg; lg >= 0; -- lg) { if (parent[lg][u] != parent[lg][v]) { u = parent[lg][u]; v = parent[lg][v]; } } return parent[0][u]; } bool isChild(int u, int p) { return in[p] <= in[u] && out[u] <= out[p]; } void solve() { g.resize(n + 1); for (int i = 1; i <= n - 1; ++ i) { int u = get<0>(edges[i]), v = get<1>(edges[i]); g[u].push_back(v); g[v].push_back(u); } Lg = __lg(n); dist[1] = 1; dfs(1, 0); for (int lg = 1; lg <= Lg; ++ lg) { for (int u = 1; u <= n; ++ u) { parent[lg][u] = parent[lg - 1][parent[lg - 1][u]]; } } for (int i = 1; i <= n - 1; ++ i) { int u = get<0>(edges[i]), v = get<1>(edges[i]); if (in[u] > in[v]) swap(u, v); edges[i] = make_tuple(u, v, get<2>(edges[i])); } while (q -- > 0) { int path, curPosition; cin >> path >> curPosition; int anc = lca(curPosition, escape); int u = get<0>(edges[path]); int v = get<1>(edges[path]); if (isChild(u, anc) && ((isChild(curPosition, u) && isChild(curPosition, v)) || (isChild(escape, u) && isChild(escape, v)))) { cout << 0; } else { cout << "escaped"; } cout << '\n'; } } } int32_t main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); cin >> n >> numStores >> q >> escape; for (int i = 1; i <= n - 1; ++ i) { int u, v, w; cin >> u >> v >> w; edges[i] = make_tuple(u, v, w); } for (int i = 1; i <= numStores; ++ i) cin >> positionStore[i]; if (sub12::check()) { sub12::solve(); return 0; } if (sub3::check()) { sub3::solve(); return 0; } return (0 ^ 0); } /// Code by vuavisao
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...