Submission #419984

#	Time	Username	Problem	Language	Result	Execution time	Memory
419984		nicolaalexandra	Valley (BOI19_valley)	C++14	100 / 100	656 ms	29204 KiB

valley

#include <bits/stdc++.h>
#define DIM 100010
#define INF 1000000000000000000LL
using namespace std;

struct segment_tree{
    long long 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];
long long 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, long long 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);
}

long long 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; long long 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);

        long long 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[y].second));
        } else {

            val = min (val,query(1,1,n,1,poz[y].first-1));
            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;
    return 1;
}

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;
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41