# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
712015 |
2023-03-18T00:17:28 Z |
Lobo |
Valley (BOI19_valley) |
C++17 |
|
234 ms |
36564 KB |
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e5+10;
int n, in[maxn], out[maxn], dp[maxn], sub[maxn], sp[maxn];
int h[maxn], d[maxn], par[maxn], timer, s, q, rt, tr[4*maxn];
vector<pair<int,int>> g[maxn], edg, qrys[maxn];
pair<int,string> ansq[maxn];
void dfsdp(int u, int ant) {
in[u] = ++timer;
dp[u] = inf;
sub[u] = 1;
if(sp[u]) dp[u] = d[u];
for(auto V : g[u]) if(V.fr != ant) {
int v = V.fr;
int w = V.sc;
h[v] = h[u]+1;
d[v] = d[u]+w;
par[v] = u;
dfsdp(v,u);
sub[u]+= sub[v];
dp[u] = min(dp[u],dp[v]);
}
out[u] = timer;
}
void build(int no, int l, int r) {
tr[no] = inf;
if(l == r) return;
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void upd(int no, int l, int r, int pos, int val) {
if(l > pos || r < pos) return;
if(l == r) {
tr[no] = val;
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
upd(lc,l,mid,pos,val);
upd(rc,mid+1,r,pos,val);
tr[no] = min(tr[lc],tr[rc]);
}
int qry(int no, int l, int r, int L, int R) {
if(l > R || r < L) return inf;
if(l >= L && r <= R) return tr[no];
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
return min(qry(lc,l,mid,L,R),qry(rc,mid+1,r,L,R));
}
void dfsqry(int u, int ant) {
if(dp[u] == inf) upd(1,0,n,h[u],inf);
else upd(1,0,n,h[u],dp[u]-2*d[u]);
for(auto X : qrys[u]) {
int id = X.fr;
int i = X.sc;
int b;
if(h[edg[id-1].fr] > h[edg[id-1].sc]) b = edg[id-1].fr;
else b = edg[id-1].sc;
if(in[b] <= in[u] && in[u] <= out[b]) {
int ans = qry(1,0,n,h[b],h[u]);
if(ans == inf) ansq[i] = mp(-1,"oo");
else ansq[i] = mp(ans+d[u],"");
}
else {
ansq[i] = mp(-1,"escaped");
}
}
for(auto V : g[u]) if(V.fr != ant) {
int v = V.fr;
dfsqry(v,u);
}
}
void solve() {
cin >> n >> s >> q >> rt;
for(int i = 1; i <= n-1; i++) {
int u,v,w; cin >> u >> v >> w;
g[u].pb(mp(v,w));
g[v].pb(mp(u,w));
edg.pb(mp(u,v));
}
for(int i = 1; i <= s; i++) {
int v; cin >> v;
sp[v] = 1;
}
dfsdp(rt,0);
for(int i = 1; i <= q; i++) {
int id, u; cin >> id >> u;
qrys[u].pb(mp(id,i));
}
build(1,0,n);
dfsqry(rt,0);
for(int i = 1; i <= q; i++) {
if(ansq[i].fr == -1) cout << ansq[i].sc << endl;
else cout << ansq[i].fr << endl;
}
// while(q--) {
// int id, u;
// cin >> id >> u;
// int b;
// if(h[edg[id-1].fr] > h[edg[id-1].sc]) b = edg[id-1].fr;
// else b = edg[id-1].sc;
// if(in[b] <= in[u] && in[u] <= out[b]) {
// int ans = inf;
// int v = u;
// while(true) {
// if(dp[v] != inf) {
// ans = min(ans, dp[v]-2*d[v]);
// }
// if(v == b) break;
// v = par[v];
// }
// if(ans == inf) cout << "oo" << endl;
// else cout << ans+d[u] << endl;
// }
// else {
// cout << "escaped" << endl;
// }
// }
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9300 KB |
Output is correct |
2 |
Correct |
8 ms |
9336 KB |
Output is correct |
3 |
Correct |
8 ms |
9340 KB |
Output is correct |
4 |
Correct |
9 ms |
9372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9300 KB |
Output is correct |
2 |
Correct |
8 ms |
9336 KB |
Output is correct |
3 |
Correct |
8 ms |
9340 KB |
Output is correct |
4 |
Correct |
9 ms |
9372 KB |
Output is correct |
5 |
Correct |
6 ms |
9088 KB |
Output is correct |
6 |
Correct |
7 ms |
9172 KB |
Output is correct |
7 |
Correct |
6 ms |
9212 KB |
Output is correct |
8 |
Correct |
6 ms |
9172 KB |
Output is correct |
9 |
Correct |
6 ms |
9084 KB |
Output is correct |
10 |
Correct |
5 ms |
9216 KB |
Output is correct |
11 |
Correct |
5 ms |
9172 KB |
Output is correct |
12 |
Correct |
6 ms |
9088 KB |
Output is correct |
13 |
Correct |
6 ms |
9148 KB |
Output is correct |
14 |
Correct |
7 ms |
9300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
31028 KB |
Output is correct |
2 |
Correct |
207 ms |
30864 KB |
Output is correct |
3 |
Correct |
194 ms |
30836 KB |
Output is correct |
4 |
Correct |
226 ms |
33080 KB |
Output is correct |
5 |
Correct |
182 ms |
33224 KB |
Output is correct |
6 |
Correct |
181 ms |
36052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9300 KB |
Output is correct |
2 |
Correct |
8 ms |
9336 KB |
Output is correct |
3 |
Correct |
8 ms |
9340 KB |
Output is correct |
4 |
Correct |
9 ms |
9372 KB |
Output is correct |
5 |
Correct |
6 ms |
9088 KB |
Output is correct |
6 |
Correct |
7 ms |
9172 KB |
Output is correct |
7 |
Correct |
6 ms |
9212 KB |
Output is correct |
8 |
Correct |
6 ms |
9172 KB |
Output is correct |
9 |
Correct |
6 ms |
9084 KB |
Output is correct |
10 |
Correct |
5 ms |
9216 KB |
Output is correct |
11 |
Correct |
5 ms |
9172 KB |
Output is correct |
12 |
Correct |
6 ms |
9088 KB |
Output is correct |
13 |
Correct |
6 ms |
9148 KB |
Output is correct |
14 |
Correct |
7 ms |
9300 KB |
Output is correct |
15 |
Correct |
208 ms |
31028 KB |
Output is correct |
16 |
Correct |
207 ms |
30864 KB |
Output is correct |
17 |
Correct |
194 ms |
30836 KB |
Output is correct |
18 |
Correct |
226 ms |
33080 KB |
Output is correct |
19 |
Correct |
182 ms |
33224 KB |
Output is correct |
20 |
Correct |
181 ms |
36052 KB |
Output is correct |
21 |
Correct |
167 ms |
29768 KB |
Output is correct |
22 |
Correct |
187 ms |
29716 KB |
Output is correct |
23 |
Correct |
207 ms |
29600 KB |
Output is correct |
24 |
Correct |
201 ms |
32088 KB |
Output is correct |
25 |
Correct |
192 ms |
35876 KB |
Output is correct |
26 |
Correct |
184 ms |
30236 KB |
Output is correct |
27 |
Correct |
180 ms |
29932 KB |
Output is correct |
28 |
Correct |
196 ms |
29932 KB |
Output is correct |
29 |
Correct |
206 ms |
31616 KB |
Output is correct |
30 |
Correct |
183 ms |
33768 KB |
Output is correct |
31 |
Correct |
168 ms |
30724 KB |
Output is correct |
32 |
Correct |
185 ms |
30520 KB |
Output is correct |
33 |
Correct |
189 ms |
30572 KB |
Output is correct |
34 |
Correct |
234 ms |
32672 KB |
Output is correct |
35 |
Correct |
180 ms |
36564 KB |
Output is correct |
36 |
Correct |
176 ms |
32816 KB |
Output is correct |