# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
670799 |
2022-12-10T14:34:04 Z |
groshi |
Valley (BOI19_valley) |
C++17 |
|
172 ms |
34364 KB |
#include<iostream>
#include<vector>
#define int long long
using namespace std;
int n,s,q,e;
struct wi{
vector<int> Q;
int pre=0,post=0;
int odl=0;
int poz=0;
bool jest=0;
int real=0;
}*w;
pair<int,int> co[200000];
vector<pair<int,int> > zap[200000];
int pree=1,postt=1;
int drzewo[1000000];
int wyn[200000];
int pot=1;
void dfs(int x,int ojc)
{
w[x].poz=w[ojc].poz+1;
w[x].pre=pree;
pree++;
w[x].real=1e18;
if(w[x].jest)
w[x].real=0;
for(int i=0;i<w[x].Q.size();i+=2)
{
int pom=w[x].Q[i];
if(pom==ojc)
continue;
w[pom].odl=w[x].odl+w[x].Q[i+1];
dfs(pom,x);
w[x].real=min(w[x].real,w[pom].real+w[x].Q[i+1]);
}
w[x].post=postt;
postt++;
}
void ustaw(int x,int co)
{
x+=pot;
drzewo[x]=co;
x/=2;
while(x>0)
{
drzewo[x]=min(drzewo[x*2],drzewo[x*2+1]);
x/=2;
}
}
int zapp(int x,int y)
{
if(y<x)
swap(x,y);
x+=pot;
y+=pot;
int wynik=min(drzewo[x],drzewo[y]);
while(x/2!=y/2)
{
if(x%2==0)
wynik=min(wynik,drzewo[x+1]);
if(y%2==1)
wynik=min(wynik,drzewo[y-1]);
x/=2;
y/=2;
}
return wynik;
}
void dfs2(int x,int ojc)
{
ustaw(w[x].poz,w[x].real-w[x].odl);
for(int i=0;i<zap[x].size();i++)
{
int kto=zap[x][i].first;
int gdzie=zap[x][i].second;
int dol;
if(w[co[gdzie].first].poz<w[co[gdzie].second].poz)
dol=co[gdzie].second;
else dol=co[gdzie].first;
if(!(w[x].pre>=w[dol].pre && w[x].post<=w[dol].post))
{
wyn[kto]=-1;
continue;
}
wyn[kto]=zapp(w[x].poz,w[dol].poz)+w[x].odl;
}
for(int i=0;i<w[x].Q.size();i+=2)
{
int pom=w[x].Q[i];
if(pom==ojc)
continue;
dfs2(pom,x);
}
ustaw(w[x].poz,1e18);
}
int32_t main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int x,y,z;
cin>>n>>s>>q>>e;
w=new wi[n+3];
while(pot<=n)
pot*=2;
pot--;
for(int i=1;i<n;i++)
{
cin>>x>>y>>z;
w[x].Q.push_back(y);
w[x].Q.push_back(z);
w[y].Q.push_back(x);
w[y].Q.push_back(z);
co[i]={x,y};
}
for(int i=1;i<=s;i++)
{
cin>>x;
w[x].jest=1;
}
for(int i=1;i<=q;i++)
{
cin>>x>>y;
zap[y].push_back({i,x});
}
dfs(e,0);
for(int i=1;i<=pot*2+1;i++)
drzewo[i]=1e18;
dfs2(e,0);
for(int i=1;i<=q;i++)
{
if(wyn[i]==-1)
cout<<"escaped\n";
else if(wyn[i]>=1e18)
cout<<"oo\n";
else cout<<wyn[i]<<"\n";
}
return 0;
}
Compilation message
valley.cpp: In function 'void dfs(long long int, long long int)':
valley.cpp:28:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i=0;i<w[x].Q.size();i+=2)
| ~^~~~~~~~~~~~~~
valley.cpp: In function 'void dfs2(long long int, long long int)':
valley.cpp:72:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i=0;i<zap[x].size();i++)
| ~^~~~~~~~~~~~~~
valley.cpp:87:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i=0;i<w[x].Q.size();i+=2)
| ~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5460 KB |
Output is correct |
2 |
Correct |
4 ms |
5424 KB |
Output is correct |
3 |
Correct |
6 ms |
5420 KB |
Output is correct |
4 |
Correct |
5 ms |
5496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5460 KB |
Output is correct |
2 |
Correct |
4 ms |
5424 KB |
Output is correct |
3 |
Correct |
6 ms |
5420 KB |
Output is correct |
4 |
Correct |
5 ms |
5496 KB |
Output is correct |
5 |
Correct |
3 ms |
5204 KB |
Output is correct |
6 |
Correct |
4 ms |
5168 KB |
Output is correct |
7 |
Correct |
4 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5204 KB |
Output is correct |
9 |
Correct |
4 ms |
5168 KB |
Output is correct |
10 |
Correct |
4 ms |
5204 KB |
Output is correct |
11 |
Correct |
4 ms |
5204 KB |
Output is correct |
12 |
Correct |
5 ms |
5204 KB |
Output is correct |
13 |
Correct |
5 ms |
5296 KB |
Output is correct |
14 |
Correct |
4 ms |
5172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
157 ms |
28664 KB |
Output is correct |
2 |
Correct |
161 ms |
28588 KB |
Output is correct |
3 |
Correct |
164 ms |
28488 KB |
Output is correct |
4 |
Correct |
171 ms |
30680 KB |
Output is correct |
5 |
Correct |
146 ms |
30916 KB |
Output is correct |
6 |
Correct |
170 ms |
33748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
5460 KB |
Output is correct |
2 |
Correct |
4 ms |
5424 KB |
Output is correct |
3 |
Correct |
6 ms |
5420 KB |
Output is correct |
4 |
Correct |
5 ms |
5496 KB |
Output is correct |
5 |
Correct |
3 ms |
5204 KB |
Output is correct |
6 |
Correct |
4 ms |
5168 KB |
Output is correct |
7 |
Correct |
4 ms |
5204 KB |
Output is correct |
8 |
Correct |
4 ms |
5204 KB |
Output is correct |
9 |
Correct |
4 ms |
5168 KB |
Output is correct |
10 |
Correct |
4 ms |
5204 KB |
Output is correct |
11 |
Correct |
4 ms |
5204 KB |
Output is correct |
12 |
Correct |
5 ms |
5204 KB |
Output is correct |
13 |
Correct |
5 ms |
5296 KB |
Output is correct |
14 |
Correct |
4 ms |
5172 KB |
Output is correct |
15 |
Correct |
157 ms |
28664 KB |
Output is correct |
16 |
Correct |
161 ms |
28588 KB |
Output is correct |
17 |
Correct |
164 ms |
28488 KB |
Output is correct |
18 |
Correct |
171 ms |
30680 KB |
Output is correct |
19 |
Correct |
146 ms |
30916 KB |
Output is correct |
20 |
Correct |
170 ms |
33748 KB |
Output is correct |
21 |
Correct |
130 ms |
28184 KB |
Output is correct |
22 |
Correct |
141 ms |
27980 KB |
Output is correct |
23 |
Correct |
147 ms |
28004 KB |
Output is correct |
24 |
Correct |
171 ms |
30552 KB |
Output is correct |
25 |
Correct |
146 ms |
34364 KB |
Output is correct |
26 |
Correct |
134 ms |
28244 KB |
Output is correct |
27 |
Correct |
143 ms |
28100 KB |
Output is correct |
28 |
Correct |
148 ms |
28080 KB |
Output is correct |
29 |
Correct |
161 ms |
29716 KB |
Output is correct |
30 |
Correct |
167 ms |
31848 KB |
Output is correct |
31 |
Correct |
138 ms |
28456 KB |
Output is correct |
32 |
Correct |
149 ms |
28092 KB |
Output is correct |
33 |
Correct |
151 ms |
28220 KB |
Output is correct |
34 |
Correct |
172 ms |
30340 KB |
Output is correct |
35 |
Correct |
146 ms |
34168 KB |
Output is correct |
36 |
Correct |
148 ms |
30412 KB |
Output is correct |