# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
915771 |
2024-01-24T16:51:43 Z |
AndrijaM |
Valley (BOI19_valley) |
C++14 |
|
467 ms |
42624 KB |
#include <bits/stdc++.h>
using namespace std;
const long long maxn=1e5+10;
const long long logn=25;
const long long mod=1e9+7;
long long n,s,q,e;
vector<pair<long long,long long>>g[maxn];
set<long long>ins;
vector<pair<long long,long long>>pr;
long long up_node[maxn][logn];
long long dep[maxn];
struct N
{
long long idx;
long long dis;
N(){}
N(long long _idx,long long _dis)
{
idx=_idx;
dis=_dis;
}
bool operator <(const N &tmp)const
{
return dis>tmp.dis;
}
};
void dfs(long long node,int par)
{
up_node[node][0]=par;
dep[node]=dep[up_node[node][0]]+1;
for(long long i=1;i<logn;i++)
{
up_node[node][i]=up_node[up_node[node][i-1]][i-1];
}
for(auto ax:g[node])
{
if(ax.first!=par)
dfs(ax.first,node);
}
}
long long UP(long long node,long long k)
{
for(long long i=0;i<logn;i++)
{
if(k&(1<<i))
{
node=up_node[node][i];
}
}
return node;
}
long long LCA(long long a,long long b)
{
if(dep[a]<dep[b])
{
swap(a,b);
}
long long k=dep[a]-dep[b];
a=UP(a,k);
if(a==b)
{
return a;
}
for(long long i=logn-1;i>=0;i--)
{
if(up_node[a][i]!=up_node[b][i])
{
a=up_node[a][i];
b=up_node[b][i];
}
}
return up_node[a][0];
}
int main()
{
cin>>n>>s>>q>>e;
memset(dep,0,sizeof dep);
memset(up_node,0,sizeof up_node);
for(long long i=0;i<n-1;i++)
{
long long a,b,c;
cin>>a>>b>>c;
g[a].push_back({b,c});
g[b].push_back({a,c});
pr.push_back({a,b});
}
dfs(1,0);
for(long long i=0;i<s;i++)
{
long long pom;
cin>>pom;
ins.insert(pom);
}
while(q--)
{
long long idxe,st;
cin>>idxe>>st;
idxe--;
long long n1=pr[idxe].first;
long long n2=pr[idxe].second;
///cout<<n1<<" "<<n2<<endl;
if(n<1100)
{
///kolku e odalecen od S
priority_queue<N>Q;
Q.push(N(st,0));
long long d[n+10];
for(long long pi=0;pi<n+10;pi++)
{
d[pi]=1e18;
}
d[st]=0;
bool ok=false;
while(!Q.empty())
{
N teme=Q.top();Q.pop();
if(teme.idx==e)
{
cout<<"escaped"<<endl;
ok=true;
break;
}
for(auto ax:g[teme.idx])
{
if((teme.idx==n1 && ax.first==n2) || (teme.idx==n2 && ax.first==n1))
{
continue;
}
if(teme.dis+ax.second<d[ax.first])
{
d[ax.first]=teme.dis+ax.second;
Q.push(N(ax.first,d[ax.first]));
}
}
}
long long ans=1e18;
for(auto pom:ins)
{
ans=min(ans, d[pom]);
}
if(!ok)
{
if(ans!=1e18)
cout<<ans<<endl;
else
{
cout<<"oo"<<endl;
}
}
}
else
{
bool ok=false;
if(LCA(n1,n2)==n1)
{
if((LCA(n2,e)==n2 && LCA(n2,st)==n2) || (LCA(n2,e)!=n2 && LCA(n2,st)!=n2))
{
ok=true;
cout<<"escaped"<<endl;
}
}
else
{
if((LCA(n1,e)==n1 && LCA(n1,st)==n1) || (LCA(n1,e)!=n1 && LCA(n1,st)!=n1))
{
ok=true;
cout<<"escaped"<<endl;
}
}
if(!ok)
{
cout<<0<<endl;
}
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
23132 KB |
Output is correct |
2 |
Correct |
28 ms |
23128 KB |
Output is correct |
3 |
Correct |
29 ms |
23132 KB |
Output is correct |
4 |
Correct |
32 ms |
23184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
23132 KB |
Output is correct |
2 |
Correct |
28 ms |
23128 KB |
Output is correct |
3 |
Correct |
29 ms |
23132 KB |
Output is correct |
4 |
Correct |
32 ms |
23184 KB |
Output is correct |
5 |
Correct |
36 ms |
23132 KB |
Output is correct |
6 |
Correct |
22 ms |
23132 KB |
Output is correct |
7 |
Correct |
23 ms |
23132 KB |
Output is correct |
8 |
Correct |
27 ms |
23236 KB |
Output is correct |
9 |
Correct |
33 ms |
23132 KB |
Output is correct |
10 |
Correct |
37 ms |
23228 KB |
Output is correct |
11 |
Correct |
19 ms |
23132 KB |
Output is correct |
12 |
Correct |
36 ms |
23128 KB |
Output is correct |
13 |
Correct |
27 ms |
23132 KB |
Output is correct |
14 |
Correct |
43 ms |
23248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
416 ms |
35024 KB |
Output is correct |
2 |
Correct |
415 ms |
39252 KB |
Output is correct |
3 |
Correct |
404 ms |
38960 KB |
Output is correct |
4 |
Correct |
467 ms |
40092 KB |
Output is correct |
5 |
Correct |
440 ms |
40120 KB |
Output is correct |
6 |
Correct |
414 ms |
42624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
23132 KB |
Output is correct |
2 |
Correct |
28 ms |
23128 KB |
Output is correct |
3 |
Correct |
29 ms |
23132 KB |
Output is correct |
4 |
Correct |
32 ms |
23184 KB |
Output is correct |
5 |
Correct |
36 ms |
23132 KB |
Output is correct |
6 |
Correct |
22 ms |
23132 KB |
Output is correct |
7 |
Correct |
23 ms |
23132 KB |
Output is correct |
8 |
Correct |
27 ms |
23236 KB |
Output is correct |
9 |
Correct |
33 ms |
23132 KB |
Output is correct |
10 |
Correct |
37 ms |
23228 KB |
Output is correct |
11 |
Correct |
19 ms |
23132 KB |
Output is correct |
12 |
Correct |
36 ms |
23128 KB |
Output is correct |
13 |
Correct |
27 ms |
23132 KB |
Output is correct |
14 |
Correct |
43 ms |
23248 KB |
Output is correct |
15 |
Correct |
416 ms |
35024 KB |
Output is correct |
16 |
Correct |
415 ms |
39252 KB |
Output is correct |
17 |
Correct |
404 ms |
38960 KB |
Output is correct |
18 |
Correct |
467 ms |
40092 KB |
Output is correct |
19 |
Correct |
440 ms |
40120 KB |
Output is correct |
20 |
Correct |
414 ms |
42624 KB |
Output is correct |
21 |
Incorrect |
354 ms |
33808 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |