| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 217702 |
2020-03-30T13:20:32 Z |
Fischer |
Valley (BOI19_valley) |
C++14 |
|
212 ms |
37860 KB |
#include <bits/stdc++.h>
#define re(x, y, z) for (int x=y; x<z; ++x)
#define trav(v, x) for (int v : x)
#define eb emplace_back
using namespace std;
const int maxn = 1e5 + 10;
long long h[maxn];
int lo[maxn], hi[maxn];
long long dist[maxn];
long long down[maxn];
using ii = pair<int, int>;
vector<ii> g[maxn];
int n, s, q, e;
ii edges[maxn];
int id[maxn];
bool shop[maxn];
const int LOG = 18;
int up[maxn][LOG];
long long st[maxn][LOG];
using lli = pair<long long, int>;
priority_queue<lli, vector<lli>, greater<lli>> Q;
const long long inf = 1e18;
int T = 0;
long long dfs(int x, int p, long long he) {
h[x] = he;
lo[x] = T++;
down[x] = shop[x] ? 0 : inf;
for (auto node : g[x]) {
if (node.first == p) continue;
dfs(node.first, x, he + node.second);
down[x] = min(down[x], down[node.first] + node.second);
}
st[x][0] = down[x] - h[x];
up[x][0] = p==-1 ? x : p;
for (int k = 1; k < LOG; ++k) {
st[x][k] = min(st[x][k-1], st[up[x][k-1]][k-1]);
up[x][k] = up[up[x][k-1]][k-1];
}
hi[x] = T++;
}
bool isParent(int x, int y) {
return lo[x] <= lo[y] and hi[y] <= hi[x];
}
void dikjstra() {
while (!Q.empty()) {
auto q = Q.top(); Q.pop();
if (q.first != dist[q.second]) continue;
for (auto node : g[q.second]) {
if (q.first + node.second < dist[node.first]) {
dist[node.first] = q.first + node.second;
id[node.first] = id[q.second];
Q.push({dist[node.first], node.first});
}
}
}
}
long long query(int x, int y) {
int len = h[x] - h[y] + 1;
long long ans = inf;
for (int k = 0; k < LOG; ++k) {
if (len & (1<<k)) {
ans = min(ans, st[x][k]);
x = up[x][k];
}
}
return ans;
}
int main() {
scanf("%d%d%d%d", &n, &s, &q, &e);
re(i, 1, n) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
g[a].eb(b, w);
g[b].eb(a, w);
edges[i] = {a, b};
}
re(i, 1, n+1)
dist[i] = inf;
re(i, 0, s) {
int c;
scanf("%d", &c);
id[c] = c;
dist[c] = 0;
shop[c] = 1;
Q.push({0, c});
}
dfs(e, 0, 0);
dikjstra();
re(i, 0, q) {
int I, R;
scanf("%d%d", &I, &R);
int a = edges[I].first, b = edges[I].second;
if (h[a] > h[b]) swap(a, b);
if (isParent(b, R)) {
if (down[b] == inf) puts("oo");
else {
if (isParent(b, id[R])) {
printf("%lld\n", dist[R]);
} else {
printf("%lld\n", query(R, b) + h[R]);
}
}
} else puts("escaped");
}
return 0;
}
Compilation message
valley.cpp: In function 'long long int dfs(int, int, long long int)':
valley.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
valley.cpp: In function 'int main()':
valley.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &s, &q, &e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &c);
~~~~~^~~~~~~~~~
valley.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &I, &R);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2816 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2816 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
197 ms |
34528 KB |
Output is correct |
| 2 |
Correct |
210 ms |
34404 KB |
Output is correct |
| 3 |
Correct |
201 ms |
34152 KB |
Output is correct |
| 4 |
Correct |
205 ms |
35816 KB |
Output is correct |
| 5 |
Correct |
212 ms |
36096 KB |
Output is correct |
| 6 |
Correct |
206 ms |
37860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2816 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
