# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
650764 |
2022-10-15T09:51:20 Z |
iulia13 |
Valley (BOI19_valley) |
C++14 |
|
493 ms |
43308 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int LG = 20;
const ll inf = 1e16;
struct ura{
int x; ll c;
};
struct ura2{
int x, y;
} edges[N];
vector <ura> g[N];
int n, s, q, e;
int h[N];
ll d[N];
int dad[N][LG];
ll dpmini[N][LG];
int shop[N];
ll mini[N];
void dfs(int nod)
{
mini[nod] = inf;
if (shop[nod])
mini[nod] = d[nod];
for (auto p : g[nod])
{
int x = p.x;
ll c = p.c;
if (x == dad[nod][0])
continue;
dad[x][0] = nod;
h[x] = h[nod] + 1;
d[x] = d[nod] + c;
dfs(x);
mini[nod] = min(mini[nod], mini[x]);
}
}
void lifting()
{
for (int j = 1; j <= 19; j++)
{
for (int i = 1; i <= n; i++)
{
dad[i][j] = dad[dad[i][j - 1]][j - 1];
dpmini[i][j] = min(dpmini[i][j - 1], dpmini[dad[i][j - 1]][j - 1]);
}
}
}
int main()
{
cin >> n >> s >> q >> e;
for (int i = 1; i < n; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
edges[i] = {a, b};
}
for (int i = 1; i <= s; i++)
{
int c;
cin >> c;
shop[c] = 1;
}
dfs(e);
for (int i = 1; i <= n; i++)
{
dpmini[i][0] = inf;
if (mini[i] != inf)
dpmini[i][0] = mini[i] = mini[i] - 2 * d[i];
}
lifting();
while(q--)
{
int ind, r;
cin >> ind >> r;
int a = edges[ind].x;
int b = edges[ind].y;
if (h[a] < h[b])
swap(a, b);
///verific daca r e in subarb a
int lg = 19; ll ans = inf;
b = r;
if (ind == 6)
ind = 6;
while (h[a] != h[b] && lg != -1)
{
if (h[dad[b][lg]] >= h[a])
{
ans = min(ans, dpmini[b][lg]);
b = dad[b][lg];
}
lg--;
}
if (b != a)
{
cout << "escaped" << '\n';
continue;
}
ans = min(ans, dpmini[b][0]);
if (ans == inf)
cout << "oo\n";
else
cout << ans + d[r] << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
2732 KB |
Output is correct |
2 |
Correct |
20 ms |
2772 KB |
Output is correct |
3 |
Correct |
19 ms |
2788 KB |
Output is correct |
4 |
Correct |
20 ms |
2832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
2732 KB |
Output is correct |
2 |
Correct |
20 ms |
2772 KB |
Output is correct |
3 |
Correct |
19 ms |
2788 KB |
Output is correct |
4 |
Correct |
20 ms |
2832 KB |
Output is correct |
5 |
Correct |
5 ms |
3028 KB |
Output is correct |
6 |
Correct |
5 ms |
2928 KB |
Output is correct |
7 |
Correct |
6 ms |
2952 KB |
Output is correct |
8 |
Correct |
4 ms |
3028 KB |
Output is correct |
9 |
Correct |
5 ms |
3028 KB |
Output is correct |
10 |
Correct |
5 ms |
2932 KB |
Output is correct |
11 |
Correct |
4 ms |
2928 KB |
Output is correct |
12 |
Correct |
5 ms |
2984 KB |
Output is correct |
13 |
Correct |
5 ms |
3064 KB |
Output is correct |
14 |
Correct |
6 ms |
3028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
390 ms |
35552 KB |
Output is correct |
2 |
Correct |
415 ms |
37080 KB |
Output is correct |
3 |
Correct |
430 ms |
37176 KB |
Output is correct |
4 |
Correct |
468 ms |
39116 KB |
Output is correct |
5 |
Correct |
477 ms |
39244 KB |
Output is correct |
6 |
Correct |
493 ms |
41268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
2732 KB |
Output is correct |
2 |
Correct |
20 ms |
2772 KB |
Output is correct |
3 |
Correct |
19 ms |
2788 KB |
Output is correct |
4 |
Correct |
20 ms |
2832 KB |
Output is correct |
5 |
Correct |
5 ms |
3028 KB |
Output is correct |
6 |
Correct |
5 ms |
2928 KB |
Output is correct |
7 |
Correct |
6 ms |
2952 KB |
Output is correct |
8 |
Correct |
4 ms |
3028 KB |
Output is correct |
9 |
Correct |
5 ms |
3028 KB |
Output is correct |
10 |
Correct |
5 ms |
2932 KB |
Output is correct |
11 |
Correct |
4 ms |
2928 KB |
Output is correct |
12 |
Correct |
5 ms |
2984 KB |
Output is correct |
13 |
Correct |
5 ms |
3064 KB |
Output is correct |
14 |
Correct |
6 ms |
3028 KB |
Output is correct |
15 |
Correct |
390 ms |
35552 KB |
Output is correct |
16 |
Correct |
415 ms |
37080 KB |
Output is correct |
17 |
Correct |
430 ms |
37176 KB |
Output is correct |
18 |
Correct |
468 ms |
39116 KB |
Output is correct |
19 |
Correct |
477 ms |
39244 KB |
Output is correct |
20 |
Correct |
493 ms |
41268 KB |
Output is correct |
21 |
Correct |
364 ms |
37872 KB |
Output is correct |
22 |
Correct |
377 ms |
37756 KB |
Output is correct |
23 |
Correct |
376 ms |
37992 KB |
Output is correct |
24 |
Correct |
409 ms |
40076 KB |
Output is correct |
25 |
Correct |
462 ms |
43140 KB |
Output is correct |
26 |
Correct |
378 ms |
38300 KB |
Output is correct |
27 |
Correct |
362 ms |
37968 KB |
Output is correct |
28 |
Correct |
408 ms |
38412 KB |
Output is correct |
29 |
Correct |
422 ms |
39844 KB |
Output is correct |
30 |
Correct |
448 ms |
41284 KB |
Output is correct |
31 |
Correct |
364 ms |
38476 KB |
Output is correct |
32 |
Correct |
377 ms |
38284 KB |
Output is correct |
33 |
Correct |
391 ms |
38568 KB |
Output is correct |
34 |
Correct |
421 ms |
40396 KB |
Output is correct |
35 |
Correct |
438 ms |
43308 KB |
Output is correct |
36 |
Correct |
419 ms |
40476 KB |
Output is correct |