This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
{
dep[node]=dep[up_node[node][0]]+1;
up_node[node][0]=par;
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |