제출 #868449

#제출 시각아이디문제언어결과실행 시간메모리
868449Nuraly_SerikbayValley (BOI19_valley)C++17
23 / 100
280 ms32700 KiB
//çalışan kazanır// #include "bits/stdc++.h" using namespace std; #define int long long #define pb push_back #define S second #define F first #define all(x) x.begin(),x.end() #define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0) int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}} const int N = 4e5 + 15; const int INF = 1e18; const int MOD = 1e9 + 7; const int MODD = 1070234587ll; const double eps = 0.0001; const int p = 87; int n, dst[N], tin[N], tout[N], q, s, t, e; pair <int, int> reb[N]; vector <pair <int, int>> g[N]; void dfs (int v, int p) { tin[v] = ++t; for (auto to: g[v]) { if (to.F == p) continue; dfs (to.F, v); dst[v] = min (dst[v], (int)(dst[to.F] + to.S)); } tout[v] = t; return; } void solution () { cin >> n >> s >> q >> e; for (int i = 1; i < n; ++ i) { int v, u, w; cin >> v >> u >> w; g[v].pb ({u, w}); g[u].pb ({v, w}); reb[i] = {v, u}; } for (int i = 1; i <= n; ++ i) dst[i] = INF; for (int i = 1; i <= s; ++ i) { int x; cin >> x; dst[x] = 0; } dfs (e, 0); while (q --) { int v, idx; cin >> v >> idx; swap (v, idx); int u = reb[idx].F, ans = INF; if (tin[u] < tin[reb[idx].S]) u = reb[idx].S; if (tin[u] <= tin[v] && tout[v] <= tout[u]) { ans = dst[v]; ans = min (ans, dst[u] + (tin[v] - tin[u])); if (ans == INF) cout << "oo\n"; else cout << ans << '\n'; } else cout << "escaped\n"; } return; } signed main() { // YOSIK(); // srand (time(0)); // freopen ("E.in", "r", stdin); // freopen ("E.out", "w", stdout); int TT = 1;// cin >> TT; for (int i = 1; i <= TT; ++ i) { // cout << "Case " << i << ": "; solution (); } 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...