# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
847341 |
2023-09-09T13:47:16 Z |
mat_jur |
Valley (BOI19_valley) |
C++17 |
|
225 ms |
43956 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define eb emplace_back
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, S, q, e;
cin >> n >> S >> q >> e;
e--;
vector<tuple<int, int, int>> kr(n-1);
vector<bool> s(n);
vector<vector<pair<int, int>>> G(n);
for (auto &[u, v, w] : kr) {
cin >> u >> v >> w;
u--; v--;
G[u].eb(make_pair(v, w));
G[v].eb(make_pair(u, w));
}
REP(i, S) {
int c;
cin >> c;
c--;
s[c] = true;
}
constexpr ll inf = 1e18;
int timer = 0;
int l = int(log2(n));
vector p(n, vector(l+1, -1));
vector minn(n, vector(l+1, inf));
vector<int> start(n), end(n);
vector<ll> d(n);
vector<ll> magic(n);
function<void(int, int)> dfs = [&](int v, int P) {
p[v][0] = P;
start[v] = timer++;
for(auto e : G[v]) {
int u = e.fi, w = e.se;
if (u == P) continue;
d[u] = d[v]+w;
dfs(u, v);
}
if (s[v]) magic[v] = d[v];
else {
magic[v] = inf;
for (auto e : G[v]) {
int u = e.fi;
if (u == P) continue;
magic[v] = min(magic[v], magic[u]);
}
}
end[v] = timer++;
};
dfs(e, -1);
REP(v, n) if(magic[v] != inf) magic[v] -= 2*d[v];
REP(i, n) {
if (p[i][0] == -1) minn[i][0] = inf;
else minn[i][0] = magic[p[i][0]];
}
FOR(j, 1, l) {
REP(i, n) {
if (p[i][j-1] != -1) {p[i][j] = p[p[i][j-1]][j-1]; minn[i][j] = min(minn[i][j-1], minn[p[i][j-1]][j-1]);}
}
}
debug(magic);
debug(p);
REP(J, q) {
int I, r;
cin >> I >> r;
I--; r--;
int a = get<0>(kr[I]), b = get<1>(kr[I]);
if (d[a] > d[b]) swap(a, b);
// cerr << a << ' ' << b << '\n';
if (!(start[b] <= start[r] && end[r] <= end[b])) {cout << "escaped \n"; continue;}
//binlift
ll mn = magic[r];
ll D = d[r];
ROF(i, l, 0) {
if (p[r][i] == -1) continue;
if (start[p[r][i]] < start[b] && end[b] < end[p[r][i]]) continue;
mn = min(mn, minn[r][i]);
r = p[r][i];
// cerr << r << '\n';
}
if (mn >= inf) cout << "oo \n";
else cout << mn+D << '\n';
// cout << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
37532 KB |
Output is correct |
2 |
Correct |
114 ms |
37200 KB |
Output is correct |
3 |
Correct |
126 ms |
37028 KB |
Output is correct |
4 |
Correct |
179 ms |
39664 KB |
Output is correct |
5 |
Correct |
139 ms |
39656 KB |
Output is correct |
6 |
Correct |
204 ms |
42536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
110 ms |
37532 KB |
Output is correct |
16 |
Correct |
114 ms |
37200 KB |
Output is correct |
17 |
Correct |
126 ms |
37028 KB |
Output is correct |
18 |
Correct |
179 ms |
39664 KB |
Output is correct |
19 |
Correct |
139 ms |
39656 KB |
Output is correct |
20 |
Correct |
204 ms |
42536 KB |
Output is correct |
21 |
Correct |
98 ms |
37620 KB |
Output is correct |
22 |
Correct |
107 ms |
37204 KB |
Output is correct |
23 |
Correct |
131 ms |
37068 KB |
Output is correct |
24 |
Correct |
152 ms |
40116 KB |
Output is correct |
25 |
Correct |
192 ms |
43956 KB |
Output is correct |
26 |
Correct |
109 ms |
37456 KB |
Output is correct |
27 |
Correct |
126 ms |
37200 KB |
Output is correct |
28 |
Correct |
140 ms |
37100 KB |
Output is correct |
29 |
Correct |
151 ms |
39164 KB |
Output is correct |
30 |
Correct |
225 ms |
41004 KB |
Output is correct |
31 |
Correct |
102 ms |
37548 KB |
Output is correct |
32 |
Correct |
111 ms |
37304 KB |
Output is correct |
33 |
Correct |
130 ms |
37384 KB |
Output is correct |
34 |
Correct |
166 ms |
39780 KB |
Output is correct |
35 |
Correct |
198 ms |
43600 KB |
Output is correct |
36 |
Correct |
153 ms |
40532 KB |
Output is correct |