# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
698862 | 2023-02-14T14:00:43 Z | nguyentunglam | Valley (BOI19_valley) | C++17 | 258 ms | 39268 KB |
#include<bits/stdc++.h> #define fi first #define se second #define endl "\n" #define ii pair<int, int> using namespace std; const int N = 1e5 + 10; int par[20][N]; long long f[20][N], d[N]; int st[N], ed[N], cnt; pair<int, int> edge[N]; vector<pair<int, int> > adj[N]; void dfs(int u) { st[u] = ++cnt; for(auto &[v, w] : adj[u]) if (v != par[0][u]) { par[0][v] = u; d[v] = d[u] + w; dfs(v); f[0][u] = min(f[0][u], f[0][v] + w); } ed[u] = cnt; } void scan(int u) { for(int j = 1; j <= 17; j++) { int anc = par[j - 1][u]; par[j][u] = par[j - 1][anc]; f[j][u] = min(f[j - 1][u], f[j - 1][anc] + d[u] - d[anc]); } for(auto &[v, w] : adj[u]) if (v != par[0][u]) scan(v); } bool inside(int p, int u) { return (st[p] <= st[u] && st[u] <= ed[p]); } int main() { #define task "" cin.tie(0) -> sync_with_stdio(0); if (fopen ("task.inp", "r")) { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); } if (fopen (task".inp", "r")) { freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); } int n, s, q, e; cin >> n >> s >> q >> e; for(int i = 1; i < n; i++) { int a, b, w; cin >> a >> b >> w; adj[a].emplace_back(b, w); adj[b].emplace_back(a, w); edge[i] = make_pair(a, b); } memset(f, 127, sizeof(f)); while (s--) { int c; cin >> c; f[0][c] = 0; } dfs(e); scan(e); while (q--) { int i, r; cin >> i >> r; auto &[u, v] = edge[i]; if (st[u] > st[v]) swap(u, v); if (inside(v, r)) { int ver = r; long long ans = 1e18; for(int j = 17; j >= 0; j--) if (inside(u, par[j][ver])) { ans = min(ans, d[r] - d[ver] + f[j][ver]); ver = par[j][ver]; } if (ans == 1e18) cout << "oo"; else cout << ans; cout << endl; } else cout << "escaped\n"; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 18444 KB | Output is correct |
2 | Correct | 12 ms | 18528 KB | Output is correct |
3 | Correct | 9 ms | 18564 KB | Output is correct |
4 | Correct | 9 ms | 18544 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 18444 KB | Output is correct |
2 | Correct | 12 ms | 18528 KB | Output is correct |
3 | Correct | 9 ms | 18564 KB | Output is correct |
4 | Correct | 9 ms | 18544 KB | Output is correct |
5 | Correct | 8 ms | 18516 KB | Output is correct |
6 | Correct | 9 ms | 18572 KB | Output is correct |
7 | Correct | 12 ms | 18572 KB | Output is correct |
8 | Correct | 10 ms | 18516 KB | Output is correct |
9 | Correct | 11 ms | 18564 KB | Output is correct |
10 | Correct | 10 ms | 18580 KB | Output is correct |
11 | Correct | 8 ms | 18564 KB | Output is correct |
12 | Correct | 9 ms | 18568 KB | Output is correct |
13 | Correct | 8 ms | 18516 KB | Output is correct |
14 | Correct | 8 ms | 18568 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 152 ms | 32292 KB | Output is correct |
2 | Correct | 166 ms | 35840 KB | Output is correct |
3 | Correct | 178 ms | 35716 KB | Output is correct |
4 | Correct | 196 ms | 37068 KB | Output is correct |
5 | Correct | 193 ms | 37156 KB | Output is correct |
6 | Correct | 258 ms | 38696 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 18444 KB | Output is correct |
2 | Correct | 12 ms | 18528 KB | Output is correct |
3 | Correct | 9 ms | 18564 KB | Output is correct |
4 | Correct | 9 ms | 18544 KB | Output is correct |
5 | Correct | 8 ms | 18516 KB | Output is correct |
6 | Correct | 9 ms | 18572 KB | Output is correct |
7 | Correct | 12 ms | 18572 KB | Output is correct |
8 | Correct | 10 ms | 18516 KB | Output is correct |
9 | Correct | 11 ms | 18564 KB | Output is correct |
10 | Correct | 10 ms | 18580 KB | Output is correct |
11 | Correct | 8 ms | 18564 KB | Output is correct |
12 | Correct | 9 ms | 18568 KB | Output is correct |
13 | Correct | 8 ms | 18516 KB | Output is correct |
14 | Correct | 8 ms | 18568 KB | Output is correct |
15 | Correct | 152 ms | 32292 KB | Output is correct |
16 | Correct | 166 ms | 35840 KB | Output is correct |
17 | Correct | 178 ms | 35716 KB | Output is correct |
18 | Correct | 196 ms | 37068 KB | Output is correct |
19 | Correct | 193 ms | 37156 KB | Output is correct |
20 | Correct | 258 ms | 38696 KB | Output is correct |
21 | Correct | 149 ms | 35564 KB | Output is correct |
22 | Correct | 170 ms | 35144 KB | Output is correct |
23 | Correct | 181 ms | 35076 KB | Output is correct |
24 | Correct | 237 ms | 36732 KB | Output is correct |
25 | Correct | 193 ms | 39268 KB | Output is correct |
26 | Correct | 147 ms | 35628 KB | Output is correct |
27 | Correct | 170 ms | 35232 KB | Output is correct |
28 | Correct | 160 ms | 35216 KB | Output is correct |
29 | Correct | 203 ms | 36428 KB | Output is correct |
30 | Correct | 209 ms | 37420 KB | Output is correct |
31 | Correct | 148 ms | 35744 KB | Output is correct |
32 | Correct | 170 ms | 35316 KB | Output is correct |
33 | Correct | 167 ms | 35268 KB | Output is correct |
34 | Correct | 223 ms | 36904 KB | Output is correct |
35 | Correct | 203 ms | 38920 KB | Output is correct |
36 | Correct | 185 ms | 36812 KB | Output is correct |