Submission #440654

#TimeUsernameProblemLanguageResultExecution timeMemory
440654BeanZValley (BOI19_valley)C++14
100 / 100
318 ms59348 KiB
// I_Love_LPL 11m #include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' const int N = 1e5 + 5; long long mod = 998244353; const int lim = 4e5 + 5; const int lg = 22; const int base = 311; const long double eps = 1e-6; struct viet{ ll u, v, w; }; vector<viet> E; ll dp[N][lg + 1], par[N][lg + 1], dep[N], a[N], dep2[N]; vector<pair<ll, ll>> node[N]; void dfs2(ll u, ll p){ for (int i = 1; i <= lg; i++){ dp[u][i] = min(dp[u][i - 1], dp[par[u][i - 1]][i - 1]); } for (auto j : node[u]){ if (j.first == p) continue; dfs2(j.first, u); } } void dfs(ll u, ll p){ for (int i = 1; i <= lg; i++){ par[u][i] = par[par[u][i - 1]][i - 1]; } dp[u][0] = 1e18; for (auto j : node[u]){ if (j.first == p) continue; par[j.first][0] = u; dep[j.first] = dep[u] + j.second; dep2[j.first] = dep2[u] + 1; dfs(j.first, u); dp[u][0] = min(dp[u][0], dp[j.first][0] + dep[j.first] + j.second - dep[u]); } if (a[u]) dp[u][0] = -dep[u]; } ll check(ll u, ll v){ ll dist = dep2[v] - dep2[u]; if (dist < 0) return 0; for (int i = 0; i <= lg; i++){ if (dist & (1 << i)){ v = par[v][i]; } } if (v == u) return 1; else return 0; } ll get(ll u, ll v){ ll dist = dep2[u] - dep2[v]; ll res = 1e18; ll dd = dep[u]; for (int i = 0; i <= lg; i++){ if (dist & (1 << i)){ res = min(res, dd + dp[u][i]); u = par[u][i]; } } res = min(res, dd + dp[u][0]); return res; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("tests.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n, s, q, e; cin >> n >> s >> q >> e; for (int i = 1; i < n; i++){ ll u, v, w; cin >> u >> v >> w; E.push_back({u, v, w}); node[u].push_back({v, w}); node[v].push_back({u, w}); } for (int i = 1; i <= s; i++){ ll x; cin >> x; a[x] = 1; } for (int i = 1; i <= n; i++){ for (int j = 1; j <= lg; j++){ dp[i][j] = 1e18; } } dfs(e, e); dfs2(e, e); while (q--){ ll u, v; cin >> v >> u; ll n1 = E[v - 1].u; ll n2 = E[v - 1].v; if (dep[n1] < dep[n2]) swap(n1, n2); if (!check(n1, u)) cout << "escaped" << endl; else { ll x = get(u, n1); if (x > 1e17) cout << "oo" << endl; else cout << x << endl; } } } /* Ans: Out: */

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("test.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...