| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 655856 |
2022-11-05T19:28:00 Z |
600Mihnea |
Valley (BOI19_valley) |
C++17 |
|
2 ms |
2644 KB |
bool home = 1;
bool verbose;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void print_lines() {
for (int i = 1; i <= 70; i++) {
cout << "#";
}
cout << "\n";
}
struct Edge {
int to;
int index;
int w;
};
const int N = (int) 1e5 + 7;
const int K = 20;
const ll INF = (ll) 1e18 + 7;
int n;
int s;
int q;
int e;
int cities[N];
vector<Edge> g[N];
int euler_tour[2 * N];
int sz;
int cnt_edges_up[N];
int first_on_tour[N];
int last_on_tour[N];
int lg2[2 * N];
int up_of_index[N];
pair<int, int> rmq[K][2 * N];
int par[N];
ll dep[N];
ll down[N];
bool is[N];
void dfs(int a, int p = 0) {
down[a] = INF;
if (is[a]) {
down[a] = 0;
}
par[a] = p;
euler_tour[++sz] = a;
first_on_tour[a] = last_on_tour[a] = sz;
for (auto &edge : g[a]) {
int b = edge.to;
int index = edge.index;
int w = edge.w;
if (b == p) {
continue;
}
dep[b] = dep[a] + w;
up_of_index[index] = b;
cnt_edges_up[b] = 1 + cnt_edges_up[a];
dfs(b, a);
down[a] = min(down[a], w + down[b]);
euler_tour[++sz] = a;
last_on_tour[a] = sz;
}
}
int get_lca(int a, int b) {
assert(1 <= a && a <= n);
assert(1 <= b && b <= n);
if (first_on_tour[a] > last_on_tour[b]) {
swap(a, b);
}
a = first_on_tour[a];
b = last_on_tour[b];
assert(1 <= a && a <= b && b <= sz);
int k = lg2[b - a + 1];
return min(rmq[k][a], rmq[k][b - (1 << k) + 1]).second;
}
int main() {
if (home) {
verbose = 1;
freopen ("___input___.txt", "r", stdin);
} else {
verbose = 0;
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
}
cin >> n >> s >> q >> e;
for (int i = 1; i < n; i++) {
int a, b, w;
cin >> a >> b >> w;
g[a].push_back({b, i, w});
g[b].push_back({a, i, w});
}
for (int i = 1; i <= s; i++) {
cin >> cities[i];
is[cities[i]] = 1;
}
dfs(e);
for (int i = 1; i <= n; i++) {
down[i] -= dep[i];
}
for (int i = 2; i <= sz; i++) {
lg2[i] = 1 + lg2[i / 2];
}
for (int i = 1; i <= sz; i++) {
rmq[0][i] = {cnt_edges_up[euler_tour[i]], euler_tour[i]};
}
for (int k = 1; (1 << k) <= sz; k++) {
for (int i = 1; i + (1 << k) - 1 <= sz; i++) {
rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
}
}
if (verbose) {
print_lines();
cout << "LOCAL DEBUGING OF LCA\n";
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
assert(get_lca(i, j) == get_lca(j, i));
}
}
for (int i = 1; i <= n; i++) {
assert(get_lca(i, i) == i);
assert(get_lca(e, i) == e);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
cout << "lca(" << i << ", " << j << ") = " << get_lca(i, j) << "\n";
}
}
print_lines();
}
for (int iq = 1; iq <= q; iq++) {
int index, c;
cin >> index >> c;
assert(1 <= index && index < n);
assert(1 <= c && c <= n);
int b = up_of_index[index];
if (get_lca(b, c) != b) {
cout << "escaped\n";
continue;
}
ll sol = down[c];
int current = c;
while (current != b) {
current = par[current];
sol = min(sol, down[current]);
}
sol += dep[c];
if (sol == INF) {
cout << "oo\n";
continue;
}
cout << sol << "\n";
}
return 0;
}
/**
**/
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:88:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | freopen ("___input___.txt", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
