#include <bits/stdc++.h>
#define DIM 100010
#define INF 1000000000
using namespace std;
struct segment_tree{
int mini,lazy;
} aint[DIM*4];
struct muchie{
int x,y,cost;
} mch[DIM];
vector <pair<int,int> > L[DIM],v[DIM];
pair <int,int> poz[DIM];
int E[DIM],level[DIM],f[DIM],dist[DIM],sol[DIM];
int n,m,q,e,i,j,x,y,cost,k;
void dfs (int nod, int tata){
E[++k] = nod;
poz[nod].first = k;
level[nod] = 1 + level[tata];
for (auto it : L[nod]){
int vecin = it.first;
if (vecin != tata){
dist[vecin] = dist[nod] + it.second;
dfs (vecin,nod);
}
}
poz[nod].second = k;
}
void build (int nod, int st, int dr){
if (st == dr){
if (f[E[st]])
aint[nod].mini = dist[E[st]];
else aint[nod].mini = INF;
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
aint[nod].mini = min (aint[nod<<1].mini, aint[(nod<<1)|1].mini);
}
void update_lazy (int nod, int st, int dr){
if (!aint[nod].lazy)
return;
if (st != dr){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
if (aint[fiu_st].mini != INF){
aint[fiu_st].mini += aint[nod].lazy;
aint[fiu_st].lazy += aint[nod].lazy;
}
if (aint[fiu_dr].mini != INF){
aint[fiu_dr].mini += aint[nod].lazy;
aint[fiu_dr].lazy += aint[nod].lazy;
}
}
aint[nod].lazy = 0;
}
void update (int nod, int st, int dr, int x, int y, int val){
if (x > y)
return;
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
if (aint[nod].mini != INF){
aint[nod].mini += val;
aint[nod].lazy += val;
update_lazy (nod,st,dr);
}
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update (nod<<1,st,mid,x,y,val);
if (y > mid)
update ((nod<<1)|1,mid+1,dr,x,y,val);
update_lazy (nod<<1,st,mid);
update_lazy ((nod<<1)|1,mid+1,dr);
aint[nod].mini = min (aint[nod<<1].mini, aint[(nod<<1)|1].mini);
}
int query (int nod, int st, int dr, int x, int y){
if (x > y)
return INF;
update_lazy (nod,st,dr);
if (x <= st && dr <= y)
return aint[nod].mini;
int mid = (st+dr)>>1, sol_st = INF, sol_dr = INF;
if (x <= mid)
sol_st = query (nod<<1,st,mid,x,y);
if (y > mid)
sol_dr = query ((nod<<1)|1,mid+1,dr,x,y);
return min (sol_st,sol_dr);
}
void dfs2 (int nod, int tata, int cost){
if (nod != 1){
update (1,1,n,1,poz[nod].first-1,cost);
update (1,1,n,poz[nod].first,poz[nod].second,-cost);
update (1,1,n,poz[nod].second+1,n,cost);
}
/// parcurg toate query-urile din nodul asta
for (auto it : v[nod]){
int x = mch[it.first].x, y = mch[it.first].y;
if (level[x] > level[y])
swap (x,y);
int val = INF;
if (poz[nod].first >= poz[y].first && poz[nod].second <= poz[y].second){
/// x e stramos => iau in calcul doar subarborele lui y
//val = min (val,query(1,1,n,poz[y].first,poz[nod].first-1));
//val = min (val,query(1,1,n,poz[nod].first+1,poz[y].second));
val = min (val,query(1,1,n,poz[y].first,poz[y].second));
} else {
/// query 1... poz[y].first-1
/*if (poz[nod].first < poz[y].first){
val = min (val,query(1,1,n,1,poz[nod].first-1));
val = min (val,query(1,1,n,poz[nod].first+1,poz[y].first-1));
} else */
val = min (val,query(1,1,n,1,poz[y].first-1));
/*if (poz[nod].first > poz[y].second){
val = min (val,query(1,1,n,poz[y].second+1,poz[nod].first-1));
val = min (val,query(1,1,n,poz[nod].first+1,n));
} else */
val = min (val,query(1,1,n,poz[y].second+1,n));
}
sol[it.second] = val;
}
for (auto it : L[nod]){
int vecin = it.first;
if (vecin != tata)
dfs2 (vecin,nod,it.second);
}
if (nod != 1){
update (1,1,n,1,poz[nod].first-1,-cost);
update (1,1,n,poz[nod].first,poz[nod].second,cost);
update (1,1,n,poz[nod].second+1,n,-cost);
}
}
int verif_exit (int idx, int nod){
int x = mch[idx].x, y = mch[idx].y, cnt = 0;
if (level[x] > level[y])
swap (x,y);
if (poz[nod].first >= poz[y].first && poz[nod].second <= poz[y].second)
cnt++;
if (poz[e].first >= poz[y].first && poz[e].second <= poz[y].second)
cnt++;
if (cnt == 1)
return 0;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>m>>q>>e;
for (i=1;i<n;i++){
cin>>x>>y>>cost;
mch[i] = {x,y,cost};
L[x].push_back(make_pair(y,cost));
L[y].push_back(make_pair(x,cost));
}
for (i=1;i<=m;i++){
cin>>x;
f[x] = 1;
}
dfs (1,0);
build (1,1,n);
for (i=1;i<=q;i++){
cin>>x>>y;
if (!verif_exit(x,y))
v[y].push_back(make_pair(x,i));
else sol[i] = -1;
}
dfs2 (1,0,0);
for (i=1;i<=q;i++){
if (sol[i] == -1)
cout<<"escaped\n";
else {
if (sol[i] == INF)
cout<<"oo\n";
else cout<<sol[i]<<"\n";
}
}
return 0;
}
Compilation message
valley.cpp: In function 'int verif_exit(int, int)':
valley.cpp:181:1: warning: control reaches end of non-void function [-Wreturn-type]
181 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
5268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
5268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
588 ms |
21684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
5268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
