# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
139852 |
2019-08-01T14:43:28 Z |
ae04071 |
Valley (BOI19_valley) |
C++11 |
|
400 ms |
22704 KB |
#include <bits/stdc++.h>
using namespace std;
using lli = long long;
const lli INF = 1e17;
struct seg_tr{
const static int MAX = 1<<17;
lli tr[MAX<<1];
void init() {
for(int i=0;i<MAX+MAX;i++) tr[i] = INF;
}
void upd(int cur,lli val) {
cur+=MAX;
tr[cur] = val;
cur>>=1;
while(cur) {
int nx=cur<<1;
tr[cur] = min(tr[nx],tr[nx+1]);
cur>>=1;
}
}
lli get(int l,int r) {
lli ret = INF;
l+=MAX; r+=MAX;
while(l<=r) {
ret = min({ret, tr[l],tr[r]});
if(l&1) l++;
if(!(r&1)) r--;
l>>=1; r>>=1;
}
return ret;
}
}st;
lli mx[100001];
int dfn[100001],out[100001],dn=0,n,m,q,r,chk[100001];
vector<pair<int,int>> adj[100001];
lli ans[100001];
int de[100001];
vector<pair<int,int>> qa[100001];
void dfs(int cur,int p) {
dfn[cur]=++dn;
mx[cur] = INF;
for(auto &it:adj[cur]) if(it.second!=p) {
dfs(it.second,cur);
mx[cur] = min(mx[cur], mx[it.second]+it.first);
}
if(chk[cur]) mx[cur] = 0;
out[cur] = dn;
}
void dfs2(int cur,int p,int d,lli w) {
st.upd(d, mx[cur]-w);
de[cur]=d;
for(auto &it:qa[cur]){
ans[it.second] = st.get(de[it.first], d) + w;
}
for(auto &it:adj[cur]) if(it.second != p) {
dfs2(it.second,cur,d+1,w+it.first);
}
st.upd(d, INF);
}
struct edge{
int u,v,w;
}ea[100001];
int main() {
scanf("%d%d%d%d",&n,&m,&q,&r);
for(int i=1;i<n;i++) {
scanf("%d%d%d",&ea[i].u,&ea[i].v,&ea[i].w);
adj[ea[i].u].push_back({ea[i].w,ea[i].v});
adj[ea[i].v].push_back({ea[i].w,ea[i].u});
}
for(int i=0;i<m;i++) {
int v;
scanf("%d",&v);
chk[v]=1;
}
dfs(r,0);
for(int i=0;i<q;i++) {
int a,b,u,v;
scanf("%d%d",&a,&b);
u = ea[a].u,v=ea[a].v;
if(dfn[u]>dfn[v]) swap(u,v);
if(dfn[b]<dfn[v] || dfn[b] > out[v]) ans[i] = -1;
else qa[b].push_back({v,i});
}
dfs2(r,0,0,0);
for(int i=0;i<q;i++) {
if(ans[i]==-1) puts("escaped");
else if(ans[i]>=INF/10) puts("oo");
else printf("%lld\n",ans[i]);
}
return 0;
}
Compilation message
valley.cpp: In function 'int main()':
valley.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&n,&m,&q,&r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&ea[i].u,&ea[i].v,&ea[i].w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&v);
~~~~~^~~~~~~~~
valley.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
5368 KB |
Output is correct |
2 |
Correct |
10 ms |
5368 KB |
Output is correct |
3 |
Correct |
11 ms |
5368 KB |
Output is correct |
4 |
Correct |
10 ms |
5368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
5368 KB |
Output is correct |
2 |
Correct |
10 ms |
5368 KB |
Output is correct |
3 |
Correct |
11 ms |
5368 KB |
Output is correct |
4 |
Correct |
10 ms |
5368 KB |
Output is correct |
5 |
Correct |
8 ms |
5112 KB |
Output is correct |
6 |
Correct |
8 ms |
5240 KB |
Output is correct |
7 |
Correct |
8 ms |
5240 KB |
Output is correct |
8 |
Correct |
9 ms |
5240 KB |
Output is correct |
9 |
Correct |
9 ms |
5240 KB |
Output is correct |
10 |
Correct |
8 ms |
5240 KB |
Output is correct |
11 |
Correct |
8 ms |
5240 KB |
Output is correct |
12 |
Correct |
8 ms |
5240 KB |
Output is correct |
13 |
Correct |
8 ms |
5240 KB |
Output is correct |
14 |
Correct |
8 ms |
5240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
19036 KB |
Output is correct |
2 |
Correct |
224 ms |
18680 KB |
Output is correct |
3 |
Correct |
218 ms |
18504 KB |
Output is correct |
4 |
Correct |
230 ms |
20648 KB |
Output is correct |
5 |
Correct |
207 ms |
19796 KB |
Output is correct |
6 |
Correct |
229 ms |
22692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
5368 KB |
Output is correct |
2 |
Correct |
10 ms |
5368 KB |
Output is correct |
3 |
Correct |
11 ms |
5368 KB |
Output is correct |
4 |
Correct |
10 ms |
5368 KB |
Output is correct |
5 |
Correct |
8 ms |
5112 KB |
Output is correct |
6 |
Correct |
8 ms |
5240 KB |
Output is correct |
7 |
Correct |
8 ms |
5240 KB |
Output is correct |
8 |
Correct |
9 ms |
5240 KB |
Output is correct |
9 |
Correct |
9 ms |
5240 KB |
Output is correct |
10 |
Correct |
8 ms |
5240 KB |
Output is correct |
11 |
Correct |
8 ms |
5240 KB |
Output is correct |
12 |
Correct |
8 ms |
5240 KB |
Output is correct |
13 |
Correct |
8 ms |
5240 KB |
Output is correct |
14 |
Correct |
8 ms |
5240 KB |
Output is correct |
15 |
Correct |
212 ms |
19036 KB |
Output is correct |
16 |
Correct |
224 ms |
18680 KB |
Output is correct |
17 |
Correct |
218 ms |
18504 KB |
Output is correct |
18 |
Correct |
230 ms |
20648 KB |
Output is correct |
19 |
Correct |
207 ms |
19796 KB |
Output is correct |
20 |
Correct |
229 ms |
22692 KB |
Output is correct |
21 |
Correct |
189 ms |
18184 KB |
Output is correct |
22 |
Correct |
203 ms |
17784 KB |
Output is correct |
23 |
Correct |
204 ms |
17552 KB |
Output is correct |
24 |
Correct |
222 ms |
20216 KB |
Output is correct |
25 |
Correct |
216 ms |
22584 KB |
Output is correct |
26 |
Correct |
187 ms |
18424 KB |
Output is correct |
27 |
Correct |
256 ms |
18060 KB |
Output is correct |
28 |
Correct |
285 ms |
17916 KB |
Output is correct |
29 |
Correct |
293 ms |
19576 KB |
Output is correct |
30 |
Correct |
209 ms |
20856 KB |
Output is correct |
31 |
Correct |
400 ms |
18552 KB |
Output is correct |
32 |
Correct |
278 ms |
18276 KB |
Output is correct |
33 |
Correct |
214 ms |
18172 KB |
Output is correct |
34 |
Correct |
218 ms |
20472 KB |
Output is correct |
35 |
Correct |
209 ms |
22704 KB |
Output is correct |
36 |
Correct |
202 ms |
19832 KB |
Output is correct |