# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
819634 |
2023-08-10T12:17:17 Z |
aryan12 |
Valley (BOI19_valley) |
C++17 |
|
121 ms |
57256 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5, LG = 17, INF = 1e18;
vector<pair<int, int> > g[N];
bool shop[N];
int lift[LG][N], tin[N], tout[N], tim = 0;
int dist_in_subtree[N];
int bestup[LG][N], tot_dist[LG][N];
void dfs(int node, int par)
{
if(shop[node])
{
dist_in_subtree[node] = 0;
}
else
{
dist_in_subtree[node] = INF;
}
tin[node] = ++tim;
lift[0][node] = par;
for(auto [to, wt]: g[node])
{
if(to == par) continue;
dfs(to, node);
tot_dist[0][to] = wt;
dist_in_subtree[node] = min(dist_in_subtree[node], dist_in_subtree[to] + wt);
bestup[0][to] = min(dist_in_subtree[to], dist_in_subtree[node] + wt);
}
tout[node] = tim;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, s, q, e;
cin >> n >> s >> q >> e;
vector<array<int, 3> > edges;
for(int i = 1; i < n; i++)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
edges.push_back({u, v, w});
}
for(int i = 1; i <= s; i++)
{
int x;
cin >> x;
shop[x] = true;
}
dist_in_subtree[0] = INF;
dfs(e, 0);
for(int i = 1; i < LG; i++)
{
for(int j = 1; j <= n; j++)
{
lift[i][j] = lift[i - 1][lift[i - 1][j]];
tot_dist[i][j] = tot_dist[i - 1][lift[i - 1][j]] + tot_dist[i - 1][j];
bestup[i][j] = min(bestup[i - 1][j], bestup[i - 1][lift[i - 1][j]] + tot_dist[i - 1][j]);
}
}
for(int i = 1; i <= q; i++)
{
int idx, node;
cin >> idx >> node;
idx -= 1;
if(tin[edges[idx][0]] <= tin[edges[idx][1]])
{
swap(edges[idx][0], edges[idx][1]);
}
if(tin[edges[idx][0]] <= tin[node] && tout[node] <= tout[edges[idx][0]])
{
if(dist_in_subtree[edges[idx][0]] >= INF)
{
cout << "oo\n";
}
else
{
if(shop[node])
{
cout << "0\n";
continue;
}
int cur_dist = 0, tot_ans = dist_in_subtree[node];
for(int j = LG - 1; j >= 0; j--)
{
// cout << "j = " << j << ", node = " << node << "\n";
// cout << lift[j][node] << "\n";
if(lift[j][node] == 0)
{
continue;
}
if(tin[lift[j][node]] <= tin[edges[idx][1]] && tout[edges[idx][1]] <= tout[lift[j][node]])
{
continue;
}
else
{
tot_ans = min(tot_ans, cur_dist + bestup[j][node]);
cur_dist += tot_dist[j][node];
node = lift[j][node];
}
}
// cout << "node = " << node << "\n";
// assert(tot_ans < INF);
cout << tot_ans << "\n";
}
}
else
{
cout << "escaped\n";
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3028 KB |
Output is correct |
2 |
Correct |
3 ms |
3156 KB |
Output is correct |
3 |
Correct |
3 ms |
3156 KB |
Output is correct |
4 |
Correct |
3 ms |
3156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3028 KB |
Output is correct |
2 |
Correct |
3 ms |
3156 KB |
Output is correct |
3 |
Correct |
3 ms |
3156 KB |
Output is correct |
4 |
Correct |
3 ms |
3156 KB |
Output is correct |
5 |
Incorrect |
2 ms |
3456 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
53112 KB |
Output is correct |
2 |
Correct |
91 ms |
53016 KB |
Output is correct |
3 |
Correct |
101 ms |
53120 KB |
Output is correct |
4 |
Correct |
106 ms |
55140 KB |
Output is correct |
5 |
Correct |
121 ms |
55192 KB |
Output is correct |
6 |
Correct |
109 ms |
57256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3028 KB |
Output is correct |
2 |
Correct |
3 ms |
3156 KB |
Output is correct |
3 |
Correct |
3 ms |
3156 KB |
Output is correct |
4 |
Correct |
3 ms |
3156 KB |
Output is correct |
5 |
Incorrect |
2 ms |
3456 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |