제출 #687534

#제출 시각아이디문제언어결과실행 시간메모리
687534stanislavpolynValley (BOI19_valley)C++17
23 / 100
132 ms19528 KiB
#include <bits/stdc++.h> #define fr(i, a, b) for (int i = (a); i <= (b); ++i) #define rf(i, a, b) for (int i = (a); i >= (b); --i) #define fe(x, y) for (auto& x : y) #define fi first #define se second #define pb push_back #define mp make_pair #define mt make_tuple #define all(x) (x).begin(), (x).end() #define pw(x) (1LL << (x)) #define sz(x) (int)(x).size() using namespace std; mt19937_64 rng(228); #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define fbo find_by_order #define ook order_of_key template <typename T> bool umn(T& a, T b) { return a > b ? a = b, 1 : 0; } template <typename T> bool umx(T& a, T b) { return a < b ? a = b, 1 : 0; } using ll = long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; template <typename T> using ve = vector<T>; const int N = 1e5 + 5; int n, s, q, root; ve<pii> g[N]; int w[N]; int p[N], pe[N]; int tin[N], tout[N], timer; int who[N]; ll dep[N]; bool mark[N]; ll dp[N]; int sz[N]; int d[N]; void dfs(int v = root, int p = 0) { ::p[v] = p; tin[v] = timer++; if (mark[v]) { dp[v] = 0; } else { dp[v] = 1e18; } sz[v] = 1; fe (to, g[v]) { if (to.fi == p) continue; dep[to.fi] = w[to.se] + dep[v]; who[to.se] = to.fi; pe[to.fi] = to.se; d[to.fi] = d[v] + 1; dfs(to.fi, v); sz[v] += sz[to.fi]; umn(dp[v], dp[to.fi] + w[to.se]); } tout[v] = timer; } bool isUpper(int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; } int top[N]; int pos[N]; ve<int> st; void hld(int v = root, int p = 0) { st.pb(v); pos[v] = sz(st) - 1; fe (to, g[v]) { if (g[v][0].fi == p || sz[to.fi] > sz[g[v][0].fi]) { swap(to, g[v][0]); } } fe (to, g[v]) { if (to.fi == p) continue; if (to.fi == g[v][0].fi) { top[to.fi] = top[v]; hld(to.fi, v); } else { top[to.fi] = to.fi; hld(to.fi, v); } } } ll add[N]; ll t[4 * N]; void build(int v = 1, int tl = 0, int tr = sz(st) - 1) { if (tl == tr) { t[v] = add[st[tl]] + dp[st[tl]]; return; } int tm = (tl + tr) >> 1; build(v << 1, tl, tm); build(v << 1 | 1, tm + 1, tr); t[v] = min(t[v << 1], t[v << 1 | 1]); } ll get(int v, int tl, int tr, int l, int r) { if (l > r) { return 1e18; } if (tl == l && tr == r) { return t[v]; } int tm = (tl + tr) >> 1; return min(get(v << 1, tl, tm, l, min(r, tm)), get(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r)); } ll get(int l, int r) { return get(1, 0, sz(st) - 1, l, r); } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else ios::sync_with_stdio(0); cin.tie(0); #endif cin >> n >> s >> q >> root; fr (i, 1, n - 1) { int a, b; cin >> a >> b >> w[i]; g[a].pb({b, i}); g[b].pb({a, i}); } fr (i, 1, s) { int x; cin >> x; mark[x] = 1; } dfs(); top[root] = root; hld(); { rf (i, sz(st) - 2, 0) { if (top[st[i + 1]] == top[st[i]]) { assert(p[st[i + 1]] == st[i]); add[st[i]] = add[st[i + 1]] + w[pe[st[i + 1]]]; } } } build(); fr (i, 1, q) { int idx, v; cin >> idx >> v; int u = who[idx]; if (!isUpper(u, v)) { cout << "escaped\n"; } else { if (mark[v]) { cout << "0\n"; continue; } // faster { int cur = v; ll best = 1e18; ll len = 0; int iter = 0; while (1) { if (isUpper(top[cur], u)) { assert(top[cur] == top[cur]); ll mn = get(pos[u], pos[cur]); mn -= add[cur]; umn(best, mn + len); break; } ll mn = get(pos[top[cur]], pos[cur]); mn -= add[cur]; umn(best, mn + len); len += add[top[cur]] - add[cur]; len += w[pe[top[cur]]]; cur = p[top[cur]]; iter++; if (iter > 10) break; // cout << cur << " " << top[cur] << " " << p[top[cur]] << "\n"; } if (best == 1e18) { cout << "oo\n"; } else { cout << best << "\n"; } } // // int cur = v; // ll best = 1e18; // ll len = 0; // while (1) { // umn(best, len + dp[cur]); // if (cur == u) { // break; // } // len += w[pe[cur]]; // cur = p[cur]; // } // // if (best == 1e18) { // cout << "oo\n"; // } else { // cout << best << "\n"; // } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...