#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+50;
const ll inf=1e18+50;
bool store[N];
bool escaped[N];
ll U[N],V[N],W[N];
ll depth[N],ct=0;
ll dp[N];
ll parent[N];
vector<pair<ll,ll>>E[N];
vector<pair<ll,ll>>query[N];
vector<ll>nodes;
ll res[N];
ll pref[N];
void DFSsetup(ll u)
{
if(store[u]==true)
{
dp[u]=0;
}
ct++;
depth[u]=ct;
pref[u]+=pref[parent[u]];
for(auto i:E[u])
{
if(i.first!=parent[u])
{
parent[i.first]=u;
pref[i.first]+=i.second;
DFSsetup(i.first);
dp[u]=min(dp[u],dp[i.first]+i.second);
}
}
ct--;
}
void DFSexit(ll u)
{
nodes.push_back(u);
for(ll i=0;i<query[u].size();i++)
{
ll x=U[query[u][i].first];
ll y=V[query[u][i].first];
if(x!=nodes[depth[x]-1] || y!=nodes[depth[y]-1])
{
escaped[query[u][i].second]=true;
}
}
for(auto i:E[u])
{
if(i.first!=parent[u])
{
DFSexit(i.first);
}
}
nodes.pop_back();
}
ll a[N],sum[N];
ll lc[2*N],rc[2*N],nc,root;
ll n;
void Build(ll &c,ll ss,ll se)
{
nc++;
c=nc;
if(ss==se)
{
sum[c]=0;
return;
}
ll mid=(ss+se)/2;
Build(lc[c],ss,mid);
Build(rc[c],mid+1,se);
sum[c]=min(sum[lc[c]],sum[rc[c]]);
}
ll Get(ll c,ll ss,ll se,ll qs,ll qe)
{
if(qs<=ss && se<=qe)
{
return sum[c];
}
if(qe<ss || se<qs)
{
return inf;
}
ll mid=(ss+se)/2;
return min(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
void Update(ll c,ll ss,ll se,ll qind,ll qval)
{
if(ss==se)
{
a[ss]=qval;
sum[c]=qval;
//printf("%i %i: %i\n",ss,se,sum[c]);
return;
}
ll mid=(ss+se)/2;
if(ss<=qind && qind<=mid)
{
Update(lc[c],ss,mid,qind,qval);
}
else
{
Update(rc[c],mid+1,se,qind,qval);
}
sum[c]=min(sum[lc[c]],sum[rc[c]]);
//printf("%i %i: %i\n",ss,se,sum[c]);
}
void DFSquery(ll u)
{
ct++;
Update(1,1,n,ct,dp[u]-pref[u]);
/*printf("%i: ",u);
for(int i=1;i<=n;i++)
{
printf("%lld ",a[i]);
}
printf("\n");*/
for(ll i=0;i<query[u].size();i++)
{
ll x=U[query[u][i].first];
ll y=V[query[u][i].first];
if(escaped[query[u][i].second]==true)
{
continue;
}
ll Root=x;
if(depth[y]>depth[x]) Root=y;
ll mn=Get(1,1,n,depth[Root],ct);
res[query[u][i].second]=pref[u]+mn;
//printf("%i %i: %lld %i\n",depth[Root],ct,mn,Root);
}
for(auto i:E[u])
{
if(i.first!=parent[u])
{
DFSquery(i.first);
}
}
Update(1,1,n,ct,0);
ct--;
}
int main()
{
ll s,q,e;
scanf("%lld%lld%lld%lld",&n,&s,&q,&e);
for(ll i=1;i<n;i++)
{
scanf("%lld%lld%lld",&U[i],&V[i],&W[i]);
E[U[i]].push_back({V[i],W[i]});
E[V[i]].push_back({U[i],W[i]});
dp[i]=inf;
}
dp[n]=inf;
for(ll i=1;i<=s;i++)
{
ll x;
scanf("%lld",&x);
store[x]=true;
}
ll ind[n+1],R[n+1];
for(ll i=1;i<=q;i++)
{
scanf("%lld%lld",&ind[i],&R[i]);
query[R[i]].push_back({ind[i],i});
}
Build(root,1,n);
DFSsetup(e);
DFSexit(e);
DFSquery(e);
/*for(int i=1;i<=n;i++)
{
printf("%i: %lld\n",i,dp[i]);
}*/
for(ll i=1;i<=q;i++)
{
if(escaped[i]==true)
{
printf("escaped\n");
}
else if(res[i]>=inf)
{
printf("oo\n");
}
else
{
printf("%lld\n",res[i]);
}
}
return 0;
}
Compilation message
valley.cpp: In function 'void DFSexit(long long int)':
valley.cpp:41:14: 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]
41 | for(ll i=0;i<query[u].size();i++)
| ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'void DFSquery(long long int)':
valley.cpp:120:14: 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]
120 | for(ll i=0;i<query[u].size();i++)
| ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | scanf("%lld%lld%lld%lld",&n,&s,&q,&e);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | scanf("%lld%lld%lld",&U[i],&V[i],&W[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | scanf("%lld",&x);
| ~~~~~^~~~~~~~~~~
valley.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | scanf("%lld%lld",&ind[i],&R[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
5032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
5032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
29884 KB |
Output is correct |
| 2 |
Correct |
244 ms |
29740 KB |
Output is correct |
| 3 |
Incorrect |
308 ms |
29724 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
5032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
