# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
134900 |
2019-07-23T11:53:06 Z |
Bodo171 |
Valley (BOI19_valley) |
C++14 |
|
599 ms |
43640 KB |
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
const long long inf=1LL*1e15;
vector< pair<int,int> > v[nmax];
vector<int> label[nmax];
long long lev[nmax],closest[nmax];
long long mn[20][nmax];
long long ans;
int tt[20][nmax];
int l[nmax],r[nmax],dpth[nmax],actual[nmax];
int nr,n,spec,q,root,i,x,y,z,j,blocat,nod,cat;
void dfs(int x)
{
int nod=0;
l[x]=++nr;
for(int i=0;i<v[x].size();i++)
if(!l[v[x][i].first])
{
nod=v[x][i].first;
tt[0][nod]=x;dpth[nod]=dpth[x]+1;
actual[label[x][i]]=nod;
lev[nod]=1LL*lev[x]+v[x][i].second;
dfs(nod);
closest[x]=min(closest[x],closest[nod]+v[x][i].second);
}
r[x]=nr;
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>spec>>q>>root;
for(i=1;i<=n-1;i++)
{
cin>>x>>y>>z;
v[x].push_back({y,z});
v[y].push_back({x,z});
label[x].push_back(i);
label[y].push_back(i);
}
for(i=1;i<=n;i++)
closest[i]=inf;
for(i=1;i<=spec;i++)
{
cin>>x;
closest[x]=0;
}
dfs(root);
for(i=1;i<=n;i++)
mn[0][i]=closest[i]-lev[i];
for(i=1;i<=16;i++)
for(j=1;j<=n;j++)
{
tt[i][j]=tt[i-1][tt[i-1][j]];
mn[i][j]=min(mn[i-1][j],mn[i-1][tt[i-1][j]]);
}
for(i=1;i<=q;i++)
{
cin>>blocat>>x;
y=actual[blocat];
if(l[y]<=l[x]&&l[x]<=r[y])
{
ans=inf;cat=dpth[x]-dpth[y]+1;nod=x;
for(int p=16;p>=0;p--)
if(((1<<p)&cat))
{
ans=min(ans,mn[p][nod]+lev[x]);
nod=tt[p][nod];
}
if(ans==inf) cout<<"oo\n";
else cout<<ans<<'\n';
}
else cout<<"escaped\n";
}
return 0;
}
Compilation message
valley.cpp: In function 'void dfs(int)':
valley.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
5368 KB |
Output is correct |
2 |
Correct |
35 ms |
5496 KB |
Output is correct |
3 |
Correct |
35 ms |
5368 KB |
Output is correct |
4 |
Correct |
35 ms |
5368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
5368 KB |
Output is correct |
2 |
Correct |
35 ms |
5496 KB |
Output is correct |
3 |
Correct |
35 ms |
5368 KB |
Output is correct |
4 |
Correct |
35 ms |
5368 KB |
Output is correct |
5 |
Correct |
12 ms |
5624 KB |
Output is correct |
6 |
Correct |
11 ms |
5624 KB |
Output is correct |
7 |
Correct |
10 ms |
5596 KB |
Output is correct |
8 |
Correct |
10 ms |
5624 KB |
Output is correct |
9 |
Correct |
10 ms |
5616 KB |
Output is correct |
10 |
Correct |
11 ms |
5608 KB |
Output is correct |
11 |
Correct |
10 ms |
5624 KB |
Output is correct |
12 |
Correct |
10 ms |
5624 KB |
Output is correct |
13 |
Correct |
10 ms |
5624 KB |
Output is correct |
14 |
Correct |
10 ms |
5624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
476 ms |
40236 KB |
Output is correct |
2 |
Correct |
491 ms |
39544 KB |
Output is correct |
3 |
Correct |
503 ms |
39308 KB |
Output is correct |
4 |
Correct |
516 ms |
41192 KB |
Output is correct |
5 |
Correct |
500 ms |
41308 KB |
Output is correct |
6 |
Correct |
546 ms |
43000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
5368 KB |
Output is correct |
2 |
Correct |
35 ms |
5496 KB |
Output is correct |
3 |
Correct |
35 ms |
5368 KB |
Output is correct |
4 |
Correct |
35 ms |
5368 KB |
Output is correct |
5 |
Correct |
12 ms |
5624 KB |
Output is correct |
6 |
Correct |
11 ms |
5624 KB |
Output is correct |
7 |
Correct |
10 ms |
5596 KB |
Output is correct |
8 |
Correct |
10 ms |
5624 KB |
Output is correct |
9 |
Correct |
10 ms |
5616 KB |
Output is correct |
10 |
Correct |
11 ms |
5608 KB |
Output is correct |
11 |
Correct |
10 ms |
5624 KB |
Output is correct |
12 |
Correct |
10 ms |
5624 KB |
Output is correct |
13 |
Correct |
10 ms |
5624 KB |
Output is correct |
14 |
Correct |
10 ms |
5624 KB |
Output is correct |
15 |
Correct |
476 ms |
40236 KB |
Output is correct |
16 |
Correct |
491 ms |
39544 KB |
Output is correct |
17 |
Correct |
503 ms |
39308 KB |
Output is correct |
18 |
Correct |
516 ms |
41192 KB |
Output is correct |
19 |
Correct |
500 ms |
41308 KB |
Output is correct |
20 |
Correct |
546 ms |
43000 KB |
Output is correct |
21 |
Correct |
452 ms |
39628 KB |
Output is correct |
22 |
Correct |
479 ms |
39040 KB |
Output is correct |
23 |
Correct |
485 ms |
38896 KB |
Output is correct |
24 |
Correct |
507 ms |
40956 KB |
Output is correct |
25 |
Correct |
538 ms |
43640 KB |
Output is correct |
26 |
Correct |
451 ms |
39548 KB |
Output is correct |
27 |
Correct |
496 ms |
39008 KB |
Output is correct |
28 |
Correct |
486 ms |
38776 KB |
Output is correct |
29 |
Correct |
517 ms |
40184 KB |
Output is correct |
30 |
Correct |
550 ms |
41568 KB |
Output is correct |
31 |
Correct |
452 ms |
39800 KB |
Output is correct |
32 |
Correct |
497 ms |
39116 KB |
Output is correct |
33 |
Correct |
491 ms |
38928 KB |
Output is correct |
34 |
Correct |
512 ms |
40832 KB |
Output is correct |
35 |
Correct |
599 ms |
43484 KB |
Output is correct |
36 |
Correct |
596 ms |
40856 KB |
Output is correct |