#include <bits/stdc++.h>
using namespace std;
#define debug(x) {cout << #x << ": "; for (auto it : x) cout << it << " ";cout << endl;}
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 100005
#define int long long
vector<vector<pair<int,int>>> graph;
bool here[MAXN];
ll tin[MAXN], tout[MAXN], depth[MAXN], val[MAXN], subTree[MAXN];
ll up[LOGN][MAXN], mn[LOGN][MAXN], depthNode[MAXN];
pair<int,int> road[MAXN];
int T = 0;
ll dfs(int node, int parent) {
tin[node] = ++T;
ll mn_depth = 1e17;
if (here[node])
mn_depth = depth[node];
for (auto u : graph[node]) {
if (u.f == parent)
continue;
depthNode[u.f] = depthNode[node] + 1;
depth[u.f] = depth[node] + u.s;
ll q = dfs(u.f, node);
mn_depth = min(mn_depth, q);
}
val[node] = mn_depth-2*depth[node];
tout[node] = ++T;
return mn_depth;
}
void dfs2(int node, int parent) {
for (auto u : graph[node]) {
if (u.f == parent)
continue;
up[0][u.f] = node;
mn[0][u.f] = val[u.f];
for (int i = 1; i < LOGN; i++) {
up[i][u.f] = up[i-1][up[i-1][u.f]];
mn[i][u.f] = min(mn[i-1][u.f], mn[i-1][up[i-1][u.f]]);
}
dfs2(u.f, node);
}
}
signed main() {
fast
int N, S, Q, E, A, B, W, p;
cin >> N >> S >> Q >> E;
graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
for (int i = 1; i < N; i++) {
cin >> A >> B >> W;
graph[A].push_back({B, W});
graph[B].push_back({A, W});
road[i] = {A, B};
}
for (int i = 0; i < S; i++) {
cin >> p;
here[p] = true;
}
dfs(E, E);
for (int i = 0; i < LOGN; i++)
for (int j = 0; j < MAXN; j++)
mn[i][j] = 1e17;
for (int i = 0; i < LOGN; i++)
up[i][E] = E, mn[i][E] = val[E];
dfs2(E, E);
for (int i = 1; i < N; i++) {
if (depth[road[i].s] > depth[road[i].f])
subTree[i] = road[i].s;
else
subTree[i] = road[i].f;
}
while (Q--) {
int road, city;
cin >> road >> city;
int sT = subTree[road];
int c = city;
if (tin[sT] <= tin[city] && tout[city] <= tout[sT]) {
ll res = 1e17;
int no_of_nodes = depthNode[city] - depthNode[sT] + 1;
for (int i = LOGN-1; i >= 0; i--) {
if ((1<<i) & no_of_nodes) {
res = min(res, mn[i][city]);
city = up[i][city];
}
}
res += depth[c];
if (res >= 1e15)
cout << "oo\n";
else
cout << res << "\n";
} else
cout << "escaped\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
16336 KB |
Output is correct |
2 |
Correct |
7 ms |
16212 KB |
Output is correct |
3 |
Correct |
8 ms |
16212 KB |
Output is correct |
4 |
Correct |
7 ms |
16212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
16336 KB |
Output is correct |
2 |
Correct |
7 ms |
16212 KB |
Output is correct |
3 |
Correct |
8 ms |
16212 KB |
Output is correct |
4 |
Correct |
7 ms |
16212 KB |
Output is correct |
5 |
Correct |
7 ms |
16468 KB |
Output is correct |
6 |
Correct |
6 ms |
16340 KB |
Output is correct |
7 |
Correct |
7 ms |
16468 KB |
Output is correct |
8 |
Correct |
6 ms |
16340 KB |
Output is correct |
9 |
Correct |
6 ms |
16408 KB |
Output is correct |
10 |
Correct |
8 ms |
16468 KB |
Output is correct |
11 |
Correct |
6 ms |
16468 KB |
Output is correct |
12 |
Correct |
7 ms |
16340 KB |
Output is correct |
13 |
Correct |
8 ms |
16468 KB |
Output is correct |
14 |
Correct |
6 ms |
16468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
124 ms |
46036 KB |
Output is correct |
2 |
Correct |
146 ms |
45976 KB |
Output is correct |
3 |
Correct |
140 ms |
46056 KB |
Output is correct |
4 |
Correct |
189 ms |
48072 KB |
Output is correct |
5 |
Correct |
150 ms |
48076 KB |
Output is correct |
6 |
Correct |
175 ms |
50252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
16336 KB |
Output is correct |
2 |
Correct |
7 ms |
16212 KB |
Output is correct |
3 |
Correct |
8 ms |
16212 KB |
Output is correct |
4 |
Correct |
7 ms |
16212 KB |
Output is correct |
5 |
Correct |
7 ms |
16468 KB |
Output is correct |
6 |
Correct |
6 ms |
16340 KB |
Output is correct |
7 |
Correct |
7 ms |
16468 KB |
Output is correct |
8 |
Correct |
6 ms |
16340 KB |
Output is correct |
9 |
Correct |
6 ms |
16408 KB |
Output is correct |
10 |
Correct |
8 ms |
16468 KB |
Output is correct |
11 |
Correct |
6 ms |
16468 KB |
Output is correct |
12 |
Correct |
7 ms |
16340 KB |
Output is correct |
13 |
Correct |
8 ms |
16468 KB |
Output is correct |
14 |
Correct |
6 ms |
16468 KB |
Output is correct |
15 |
Correct |
124 ms |
46036 KB |
Output is correct |
16 |
Correct |
146 ms |
45976 KB |
Output is correct |
17 |
Correct |
140 ms |
46056 KB |
Output is correct |
18 |
Correct |
189 ms |
48072 KB |
Output is correct |
19 |
Correct |
150 ms |
48076 KB |
Output is correct |
20 |
Correct |
175 ms |
50252 KB |
Output is correct |
21 |
Correct |
115 ms |
49380 KB |
Output is correct |
22 |
Correct |
129 ms |
49100 KB |
Output is correct |
23 |
Correct |
139 ms |
49356 KB |
Output is correct |
24 |
Correct |
163 ms |
51416 KB |
Output is correct |
25 |
Correct |
179 ms |
54476 KB |
Output is correct |
26 |
Correct |
116 ms |
49524 KB |
Output is correct |
27 |
Correct |
137 ms |
49200 KB |
Output is correct |
28 |
Correct |
137 ms |
49500 KB |
Output is correct |
29 |
Correct |
193 ms |
50916 KB |
Output is correct |
30 |
Correct |
181 ms |
52496 KB |
Output is correct |
31 |
Correct |
121 ms |
49488 KB |
Output is correct |
32 |
Correct |
127 ms |
49296 KB |
Output is correct |
33 |
Correct |
140 ms |
49648 KB |
Output is correct |
34 |
Correct |
176 ms |
51520 KB |
Output is correct |
35 |
Correct |
170 ms |
54396 KB |
Output is correct |
36 |
Correct |
159 ms |
51532 KB |
Output is correct |