# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
528756 |
2022-02-21T10:21:36 Z |
kderylo |
Valley (BOI19_valley) |
C++17 |
|
211 ms |
45036 KB |
#include <iostream>
#include <vector>
using namespace std;
const int stala=1e5+10;
vector<int>wektor[stala];
vector<long long>stopien[stala];
bool czy_sklep[stala];
long long dp[stala];
int ojciec[stala];
int krawedzie[stala][2];
int t[stala][2];
long long odl_ojciec[stala];
long long glebokosc[stala];
int gl[stala];
int ancestor[stala][17];
long long ans[stala][17];
int ti=0;
void dfs(int k,int p,long long odl)
{
ojciec[k]=p;
odl_ojciec[k]=odl;
ti++;
t[k][0]=ti;
if(czy_sklep[k]==0)
{
dp[k]=1e18;
}
for(int i=0;i<(int)wektor[k].size();i++)
{
if(wektor[k][i]!=p)
{
glebokosc[wektor[k][i]]=glebokosc[k]+stopien[k][i];
gl[wektor[k][i]]=gl[k]+1;
dfs(wektor[k][i],k,stopien[k][i]);
dp[k]=min(dp[k],dp[wektor[k][i]]+stopien[k][i]);
}
}
t[k][1]=ti;
}
void ustaw_lca(int ile)
{
for(int i=1;i<=ile;i++)
{
ancestor[i][0]=ojciec[i];
ans[i][0]=dp[i];
}
for(int i=1;i<=16;i++)
{
for(int j=1;j<=ile;j++)
{
ancestor[j][i]=ancestor[ancestor[j][i-1]][i-1];
int w=ancestor[j][i-1];
ans[j][i]=min(ans[j][i-1],ans[w][i-1]+glebokosc[j]-glebokosc[w]);
}
}
}
long long znajdz(int ile_w_gore,int start)
{
long long minimum=1e18;
int index=start;
for(int i=16;i>=0;i--)
{
if((1<<i)<=ile_w_gore)
{
ile_w_gore-=(1<<i);
minimum=min(minimum,ans[index][i]+glebokosc[start]-glebokosc[index]);
index=ancestor[index][i];
}
}
return minimum;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int ile,sklepy,zap,start;
cin>>ile>>sklepy>>zap>>start;
for(int i=1;i<=ile-1;i++)
{
int a,b;
long long c;
cin>>a>>b>>c;
krawedzie[i][0]=a;
krawedzie[i][1]=b;
wektor[a].push_back(b);
wektor[b].push_back(a);
stopien[a].push_back(c);
stopien[b].push_back(c);
}
for(int i=1;i<=sklepy;i++)
{
int a;
cin>>a;
czy_sklep[a]=1;
}
gl[start]=1;
dfs(start,0,0);
ustaw_lca(ile);
for(int i=1;i<=zap;i++)
{
int nr,wierzcholek,w;
cin>>nr>>wierzcholek;
if(ojciec[krawedzie[nr][0]]==krawedzie[nr][1])
{
w=krawedzie[nr][0];
}
else
{
w=krawedzie[nr][1];
}
if(t[w][0]<=t[wierzcholek][0]&&t[wierzcholek][0]<=t[w][1])
{
long long wyn=znajdz(gl[wierzcholek]-gl[w]+1,wierzcholek);
if(wyn==1e18)
{
cout<<"oo"<<"\n";
}
else
{
cout<<wyn<<"\n";
}
}
else
{
cout<<"escaped"<<"\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5196 KB |
Output is correct |
2 |
Correct |
4 ms |
5160 KB |
Output is correct |
3 |
Correct |
5 ms |
5160 KB |
Output is correct |
4 |
Correct |
5 ms |
5196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5196 KB |
Output is correct |
2 |
Correct |
4 ms |
5160 KB |
Output is correct |
3 |
Correct |
5 ms |
5160 KB |
Output is correct |
4 |
Correct |
5 ms |
5196 KB |
Output is correct |
5 |
Correct |
4 ms |
5324 KB |
Output is correct |
6 |
Correct |
4 ms |
5304 KB |
Output is correct |
7 |
Correct |
4 ms |
5324 KB |
Output is correct |
8 |
Correct |
5 ms |
5420 KB |
Output is correct |
9 |
Correct |
3 ms |
5348 KB |
Output is correct |
10 |
Correct |
4 ms |
5420 KB |
Output is correct |
11 |
Correct |
4 ms |
5324 KB |
Output is correct |
12 |
Correct |
3 ms |
5324 KB |
Output is correct |
13 |
Correct |
4 ms |
5324 KB |
Output is correct |
14 |
Correct |
4 ms |
5324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
41640 KB |
Output is correct |
2 |
Correct |
197 ms |
41108 KB |
Output is correct |
3 |
Correct |
172 ms |
40864 KB |
Output is correct |
4 |
Correct |
182 ms |
42564 KB |
Output is correct |
5 |
Correct |
203 ms |
42856 KB |
Output is correct |
6 |
Correct |
211 ms |
44544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5196 KB |
Output is correct |
2 |
Correct |
4 ms |
5160 KB |
Output is correct |
3 |
Correct |
5 ms |
5160 KB |
Output is correct |
4 |
Correct |
5 ms |
5196 KB |
Output is correct |
5 |
Correct |
4 ms |
5324 KB |
Output is correct |
6 |
Correct |
4 ms |
5304 KB |
Output is correct |
7 |
Correct |
4 ms |
5324 KB |
Output is correct |
8 |
Correct |
5 ms |
5420 KB |
Output is correct |
9 |
Correct |
3 ms |
5348 KB |
Output is correct |
10 |
Correct |
4 ms |
5420 KB |
Output is correct |
11 |
Correct |
4 ms |
5324 KB |
Output is correct |
12 |
Correct |
3 ms |
5324 KB |
Output is correct |
13 |
Correct |
4 ms |
5324 KB |
Output is correct |
14 |
Correct |
4 ms |
5324 KB |
Output is correct |
15 |
Correct |
158 ms |
41640 KB |
Output is correct |
16 |
Correct |
197 ms |
41108 KB |
Output is correct |
17 |
Correct |
172 ms |
40864 KB |
Output is correct |
18 |
Correct |
182 ms |
42564 KB |
Output is correct |
19 |
Correct |
203 ms |
42856 KB |
Output is correct |
20 |
Correct |
211 ms |
44544 KB |
Output is correct |
21 |
Correct |
158 ms |
41048 KB |
Output is correct |
22 |
Correct |
166 ms |
40412 KB |
Output is correct |
23 |
Correct |
177 ms |
40260 KB |
Output is correct |
24 |
Correct |
189 ms |
42264 KB |
Output is correct |
25 |
Correct |
208 ms |
45036 KB |
Output is correct |
26 |
Correct |
178 ms |
41156 KB |
Output is correct |
27 |
Correct |
153 ms |
40540 KB |
Output is correct |
28 |
Correct |
165 ms |
40352 KB |
Output is correct |
29 |
Correct |
183 ms |
41652 KB |
Output is correct |
30 |
Correct |
193 ms |
43144 KB |
Output is correct |
31 |
Correct |
145 ms |
41152 KB |
Output is correct |
32 |
Correct |
183 ms |
40592 KB |
Output is correct |
33 |
Correct |
167 ms |
40444 KB |
Output is correct |
34 |
Correct |
201 ms |
42212 KB |
Output is correct |
35 |
Correct |
198 ms |
45024 KB |
Output is correct |
36 |
Correct |
169 ms |
42300 KB |
Output is correct |