oj.uz

답안 #419984

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
419984 2021-06-07T20:57:06 Z nicolaalexandra Valley (BOI19_valley) C++14
100 / 100
 656 ms 29204 KB 
#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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5196 KB Output is correct
2 Correct 9 ms 5196 KB Output is correct
3 Correct 9 ms 5196 KB Output is correct
4 Correct 12 ms 5296 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5196 KB Output is correct
2 Correct 9 ms 5196 KB Output is correct
3 Correct 9 ms 5196 KB Output is correct
4 Correct 12 ms 5296 KB Output is correct
5 Correct 6 ms 5144 KB Output is correct
6 Correct 6 ms 5196 KB Output is correct
7 Correct 6 ms 5196 KB Output is correct
8 Correct 6 ms 5196 KB Output is correct
9 Correct 6 ms 5196 KB Output is correct
10 Correct 6 ms 5144 KB Output is correct
11 Correct 6 ms 5152 KB Output is correct
12 Correct 6 ms 5096 KB Output is correct
13 Correct 6 ms 5128 KB Output is correct
14 Correct 6 ms 5196 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 551 ms 19524 KB Output is correct
2 Correct 545 ms 22964 KB Output is correct
3 Correct 592 ms 22844 KB Output is correct
4 Correct 607 ms 25212 KB Output is correct
5 Correct 556 ms 23972 KB Output is correct
6 Correct 656 ms 29204 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5196 KB Output is correct
2 Correct 9 ms 5196 KB Output is correct
3 Correct 9 ms 5196 KB Output is correct
4 Correct 12 ms 5296 KB Output is correct
5 Correct 6 ms 5144 KB Output is correct
6 Correct 6 ms 5196 KB Output is correct
7 Correct 6 ms 5196 KB Output is correct
8 Correct 6 ms 5196 KB Output is correct
9 Correct 6 ms 5196 KB Output is correct
10 Correct 6 ms 5144 KB Output is correct
11 Correct 6 ms 5152 KB Output is correct
12 Correct 6 ms 5096 KB Output is correct
13 Correct 6 ms 5128 KB Output is correct
14 Correct 6 ms 5196 KB Output is correct
15 Correct 551 ms 19524 KB Output is correct
16 Correct 545 ms 22964 KB Output is correct
17 Correct 592 ms 22844 KB Output is correct
18 Correct 607 ms 25212 KB Output is correct
19 Correct 556 ms 23972 KB Output is correct
20 Correct 656 ms 29204 KB Output is correct
21 Correct 481 ms 22504 KB Output is correct
22 Correct 492 ms 22352 KB Output is correct
23 Correct 504 ms 22004 KB Output is correct
24 Correct 525 ms 23604 KB Output is correct
25 Correct 537 ms 26916 KB Output is correct
26 Correct 509 ms 22668 KB Output is correct
27 Correct 496 ms 22416 KB Output is correct
28 Correct 518 ms 22272 KB Output is correct
29 Correct 549 ms 24440 KB Output is correct
30 Correct 588 ms 26052 KB Output is correct
31 Correct 504 ms 22976 KB Output is correct
32 Correct 515 ms 22596 KB Output is correct
33 Correct 530 ms 22576 KB Output is correct
34 Correct 561 ms 24348 KB Output is correct
35 Correct 573 ms 26548 KB Output is correct
36 Correct 527 ms 24388 KB Output is correct