oj.uz

Submission #424437

# Submission time Handle Problem Language Result Execution time Memory
424437 2021-06-11T23:56:20 Z Odavey Valley (BOI19_valley) C++17
100 / 100
 654 ms 96600 KB 
//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            200005
#define mp              make_pair
#define mod7            1000000007
#define modpi           314159
#define PI              3.141592653589793238
#define pb              push_back
#define FastIO          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a)          a.begin(),a.end()
#define fi              first
#define se              second
#define ll              long long int
#define ull             unsigned long long int

int kx[8]  =            {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8]  =            {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] =            {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] =            {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] =            {+0, +0, +1, -1};
int dy4[4] =            {+1, -1, +0, +0};

ll gcd(ull a, ull b){
    return (a==0)?b:gcd(b%a,a);
}

ll lcm(ull a, ull b){
    return a*(b/gcd(a,b));
}

const long long INF = 1e18;

using namespace std;

int _in[MX_N], _out[MX_N];
int glit = 0;

ll mass[MX_N];
vector<pair<int, int> > adj[MX_N];
int p[MX_N];
int c[MX_N];

ll depth[MX_N];
ll minn[MX_N];//The cost of choosing this node as the "LCA". ie the second part of dist[u] + dist[v] - 2*dist[w]
int jump[MX_N][48];
ll minn_jump[MX_N][48];//The minimum cost value in the step above at
bool shoppe[MX_N];

void DFS(int at){
    _in[at] = glit++;
    minn[at] = INF;
    for(auto& [to, id] : adj[at]){
        if(p[at] == to){
            continue;
        }
        c[id] = to;
        p[to] = at;
        depth[to] = mass[id] + depth[at];
        DFS(to);
        minn[at] = min(minn[at], minn[to]);
    }
    if(shoppe[at]){
        minn[at] = depth[at];
    }
    _out[at] = glit++;
    return;
}

bool desc(int a, int b){
    return(_in[a] >= _in[b] && _out[a] <= _out[b]);
}

int main(){
    memset(shoppe, 0, sizeof(shoppe));
    memset(jump, -1, sizeof(jump));
    int n, s, Q, E;
    cin >> n >> s >> Q >> E;
    --E;
    p[E] = -1;
    depth[E] = 0ll;
    for(int i=0;i<n-1;++i){
        int A, B;
        cin >> A >> B >> mass[i];
        --A, --B;
        adj[A].pb({B, i});
        adj[B].pb({A, i});
    }
    for(int i=0;i<s;++i){
        int at;
        cin >> at;
        --at;
        shoppe[at] = true;
    }
    DFS(E);

    for(int at=0;at<n;++at){
        if(minn[at] != INF){
            minn[at] -= 2ll*depth[at];
        }
        jump[at][0] = p[at];
        minn_jump[at][0] = minn[at];
    }
    for(int k=1;k<48;++k){
        for(int at=0;at<n;++at){
            if(jump[at][k-1] == -1){
                jump[at][k] = -1;
                minn_jump[at][k] = INF;
            }else{
                jump[at][k] = jump[jump[at][k-1]][k-1];
                minn_jump[at][k] = min(minn_jump[at][k-1], minn_jump[jump[at][k-1]][k-1]);
            }
        }
    }
//    cout << "minn:\n";
//    for(int i=0;i<n;++i){
//        cout << minn[i] << endl;
//    }
//    cout << "jump:\n";
//    for(int i=0;i<n;++i){
//        for(int k=0;k<4;++k){
//            cout << jump[i][k] << ' ';
//        }
//        cout << endl;
//    }
//    cout << "minn_jump\n";
//    for(int i=0;i<n;++i){
//        for(int k=0;k<4;++k){
//            cout << minn_jump[i][k] << ' ';
//        }
//        cout << endl;
//    }

    for(int q=0;q<Q;++q){
        int r, v;
        cin >> r >> v;
        --r, --v;
        if(!desc(v, c[r])){
            cout << "escaped\n";
            continue;
        }
        int at = v;
        ll ans = min(minn[v], minn[c[r]]);
        for(int k=47;~k;--k){
            if(jump[at][k] == -1){
                continue;
            }
            if(!desc(jump[at][k], c[r])){
                continue;
            }
            ans = min(ans, minn_jump[at][k]);
            at = jump[at][k];
        }
        if(ans == INF){
            cout << "oo\n";
        }else{
            cout << depth[v] + ans << endl;
        }
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 42828 KB Output is correct
2 Correct 48 ms 42876 KB Output is correct
3 Correct 40 ms 42868 KB Output is correct
4 Correct 41 ms 42800 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 42828 KB Output is correct
2 Correct 48 ms 42876 KB Output is correct
3 Correct 40 ms 42868 KB Output is correct
4 Correct 41 ms 42800 KB Output is correct
5 Correct 23 ms 43276 KB Output is correct
6 Correct 26 ms 43208 KB Output is correct
7 Correct 22 ms 43212 KB Output is correct
8 Correct 23 ms 43272 KB Output is correct
9 Correct 23 ms 43268 KB Output is correct
10 Correct 23 ms 43164 KB Output is correct
11 Correct 23 ms 43268 KB Output is correct
12 Correct 23 ms 43212 KB Output is correct
13 Correct 23 ms 43208 KB Output is correct
14 Correct 26 ms 43212 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 88828 KB Output is correct
2 Correct 548 ms 88480 KB Output is correct
3 Correct 565 ms 88472 KB Output is correct
4 Correct 633 ms 90308 KB Output is correct
5 Correct 615 ms 90384 KB Output is correct
6 Correct 654 ms 92176 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 42828 KB Output is correct
2 Correct 48 ms 42876 KB Output is correct
3 Correct 40 ms 42868 KB Output is correct
4 Correct 41 ms 42800 KB Output is correct
5 Correct 23 ms 43276 KB Output is correct
6 Correct 26 ms 43208 KB Output is correct
7 Correct 22 ms 43212 KB Output is correct
8 Correct 23 ms 43272 KB Output is correct
9 Correct 23 ms 43268 KB Output is correct
10 Correct 23 ms 43164 KB Output is correct
11 Correct 23 ms 43268 KB Output is correct
12 Correct 23 ms 43212 KB Output is correct
13 Correct 23 ms 43208 KB Output is correct
14 Correct 26 ms 43212 KB Output is correct
15 Correct 541 ms 88828 KB Output is correct
16 Correct 548 ms 88480 KB Output is correct
17 Correct 565 ms 88472 KB Output is correct
18 Correct 633 ms 90308 KB Output is correct
19 Correct 615 ms 90384 KB Output is correct
20 Correct 654 ms 92176 KB Output is correct
21 Correct 535 ms 92120 KB Output is correct
22 Correct 544 ms 91844 KB Output is correct
23 Correct 558 ms 91772 KB Output is correct
24 Correct 565 ms 93844 KB Output is correct
25 Correct 570 ms 96600 KB Output is correct
26 Correct 508 ms 92096 KB Output is correct
27 Correct 540 ms 91860 KB Output is correct
28 Correct 548 ms 91768 KB Output is correct
29 Correct 558 ms 93072 KB Output is correct
30 Correct 591 ms 94552 KB Output is correct
31 Correct 560 ms 92160 KB Output is correct
32 Correct 545 ms 92048 KB Output is correct
33 Correct 542 ms 91920 KB Output is correct
34 Correct 579 ms 93716 KB Output is correct
35 Correct 577 ms 96444 KB Output is correct
36 Correct 553 ms 93892 KB Output is correct