#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+50;
const ll inf=1e16+50;
bool store[N];
bool escaped[N];
int U[N],V[N],W[N];
int depth[N],ct=0;
ll dp[N];
int parent[N];
vector<pair<int,int>>E[N];
vector<pair<int,int>>query[N];
vector<int>nodes;
ll res[N];
ll pref[N];
void DFSsetup(int 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(int u)
{
nodes.push_back(u);
for(int i=0;i<query[u].size();i++)
{
int x=U[query[u][i].first];
int 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];
int lc[2*N],rc[2*N],nc,root;
int n;
void Build(int &c,int ss,int se)
{
nc++;
c=nc;
if(ss==se)
{
sum[c]=0;
return;
}
int 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(int c,int ss,int se,int qs,int qe)
{
if(qs<=ss && se<=qe)
{
return sum[c];
}
if(qe<ss || se<qs)
{
return inf;
}
int mid=(ss+se)/2;
return min(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
void Update(int c,int ss,int se,int qind,ll qval)
{
if(ss==se)
{
a[ss]=qval;
sum[c]=qval;
//printf("%i %i: %i\n",ss,se,sum[c]);
return;
}
int 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(int 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(int i=0;i<query[u].size();i++)
{
int x=U[query[u][i].first];
int y=V[query[u][i].first];
if(escaped[query[u][i].second]==true)
{
continue;
}
int 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()
{
int s,q,e;
scanf("%i%i%i%i",&n,&s,&q,&e);
for(int i=1;i<n;i++)
{
scanf("%i%i%i",&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(int i=1;i<=s;i++)
{
int x;
scanf("%i",&x);
store[x]=true;
}
int ind[n+1],R[n+1];
for(int i=1;i<=q;i++)
{
scanf("%i%i",&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(int 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(int)':
valley.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i=0;i<query[u].size();i++)
| ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'void DFSquery(int)':
valley.cpp:120:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int 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("%i%i%i%i",&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("%i%i%i",&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("%i",&x);
| ~~~~~^~~~~~~~~
valley.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | scanf("%i%i",&ind[i],&R[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
194 ms |
20036 KB |
Output is correct |
| 2 |
Correct |
188 ms |
21280 KB |
Output is correct |
| 3 |
Incorrect |
232 ms |
21116 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
