제출 #687521

#제출 시각아이디문제언어결과실행 시간메모리
687521stanislavpolynValley (BOI19_valley)C++17
36 / 100
3069 ms17288 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]; void dfs(int v = root, int p = 0) { ::p[v] = p; tin[v] = timer++; if (mark[v]) { dp[v] = 0; } else { dp[v] = 1e18; } 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; dfs(to.fi, v); 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 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(); fr (i, 1, q) { int idx, v; cin >> idx >> v; int u = who[idx]; if (!isUpper(u, v)) { cout << "escaped\n"; } else { 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...