| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 498143 |
2021-12-24T12:34:58 Z |
Mukhitali |
Valley (BOI19_valley) |
C++17 |
|
142 ms |
33780 KB |
//bit chass 1
#include <bits/stdc++.h>
#define x first
#define y second
#define el "\n"
#define ll long long
#define pb push_back
#define pll pair <ll, ll>
#define pii pair <int, int>
#define all(x) x.begin(), x.end()
#define lcm(x,y) x * y / __gcd(x, y)
#define ibase ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
const int N = 1e5 + 5, inf = 1e9 + 7, M = 2e6, K = 300;
const ll MI = 2e18, mm = 1e15 + 5;
const double P = 3.14;
int n, s, q, e, p, tim = 1, tin[N], tout[N], up[N][20];
ll dist[N], dp[N], mn[N][20];
bool ok, c[N];
vector <pair <int, int>> g[N];
pair <int, int> ed[N];
void dfs(int v, int pr = 0) {
tin[v] = tim++;
if (c[v])
dp[v] = 0;
up[v][0] = pr;
for (int i = 1; i < 20; i++)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto to : g[v]) {
if (to.x != pr) {
dist[to.x] = dist[v] + to.y;
dfs(to.x, v);
dp[v] = min(dp[to.x] + to.y, dp[v]);
}
}
tout[tim]++;
}
void dfs2(int v, int pr) {
mn[v][0] = dp[pr] - dist[pr];
for (int i = 1; i < 20; i++)
mn[v][i] = min(mn[up[v][i - 1]][i - 1], mn[v][i - 1]);
for (pii to : g[v])
if (to.x != pr)
dfs2(to.x, v);
}
bool upper(int x, int y) {
return (tin[x] < tin[y] && tout[y] < tout[x]);
}
void solve() {
cin >> n >> s >> q >> e;
for (int i = 1, x, y, w; i < n; i++) {
cin >> x >> y >> w;
g[x].pb({y, w});
g[y].pb({x, w});
ed[i] = {x, y};
dp[i] = dp[i + 1] = mm;
}
for (int i = 1, x; i <= s; i++) {
cin >> x;
c[x] = 1;
}
dfs(e);
dfs2(e, 0);
while (q--) {
int i, r, v;
cin >> i >> r;
pii x = ed[i];
if (tin[x.x] <= tin[x.y])
v = x.y;
else
v = x.x;
if (tin[v] <= tin[r] && tout[r] <= tout[v]) {
if (v == r) {
if (dp[v] == mm)
cout << "oo" << el;
else
cout << dp[v] << el;
continue;
}
ll ans = mm, rr = r;
for (int i = 19; i >= 0; i--) {
if (up[r][i] != 0 && !upper(up[r][i], v))
ans = min(mn[r][i], ans), r = up[r][i];
}
ans = min(ans, mn[r][0]);
if (ans == mm && dp[rr] == mm)
cout << "oo" << el;
else
cout << min(ans + dist[rr], dp[rr]) << el;
}
else {
cout << "escaped" << el;
}
}
}
int main() {
ibase;
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++) {
// cout << "Case " << i << ": ";
solve();
cout << el;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
33780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
