Submission #879532

#TimeUsernameProblemLanguageResultExecution timeMemory
879532phongcdValley (BOI19_valley)C++17
23 / 100
209 ms53648 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define ii pair <int, int> #define ill pair <ll, ll> #define ild pair <ld, ld> #define fi first #define se second #define all(x) x.begin(), x.end() #define file "test" using namespace std; const int N = 2e5 + 2; const int M = 20; const ll MOD = 1e9 + 7; const ll INF = 1e18; const ll base = 311; const int BLOCK_SIZE = 400; int n, s, q, e; ii a[N]; ll w[N], f[N], d[N]; ll h[N], up[N][20], fu[N][20]; vector <int> g[N]; void dfs(int u, int p) { for (int i: g[u]) { int v = a[i].fi ^ a[i].se ^ u; if (v == p) continue; h[v] = h[u] + 1; d[v] = d[u] + w[i]; up[v][0] = u; for (int j = 1; j < M; j ++) up[v][j] = up[up[v][j - 1]][j - 1]; dfs(v, u); f[u] = min(f[u], f[v] + w[i]); } } void dfs2(int u, int p) { for (int i: g[u]) { int v = a[i].fi ^ a[i].se ^ u; if (v == p) continue; fu[v][0] = f[u] - d[u]; for (int j = 1; j < M; j ++) fu[v][j] = min(fu[v][j - 1], fu[up[v][j - 1]][j - 1]); dfs2(v, u); } } int jump(int u, int k) { for (int j = 0; j < M; j ++) if (k >> j & 1) u = up[u][j]; return u; } bool is_anc(int u, int p) { return jump(u, h[u] - h[p]) == p; } ll get(int u, int k) { ll res = INF; for (int j = 0; j < M; j ++) res = min(res, fu[u][j]), u = up[u][j]; return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> s >> q >> e; for (int i = 1; i < n; i ++) { cin >> a[i].fi >> a[i].se >> w[i]; f[i] = INF; g[a[i].fi].push_back(i); g[a[i].se].push_back(i); } f[n] = INF; for (int i = 0, u; i < s; i ++) cin >> u, f[u] = 0; for (int i = 0; i < 20; i ++) for (int j = 1; j <= n; j ++) fu[j][i] = INF; dfs(e, 0); dfs2(e, 0); for (int i = 1; i < n; i ++) { auto [u, v] = a[i]; if (h[u] < h[v]) swap(a[i].fi, a[i].se); } while (q --) { int i, r; cin >> i >> r; int u = a[i].fi; if (!is_anc(r, u)) cout << "escaped\n"; else if (f[u] == INF) cout << "oo\n"; else cout << min(d[r] + get(r, h[r] - h[u]), f[r]) << '\n'; } } /* /\_/\ zzZ (= -_-) / >u >u */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...