oj.uz

Submission #424436

# Submission time Handle Problem Language Result Execution time Memory
424436 2021-06-11T23:55:08 Z Odavey Valley (BOI19_valley) C++17
36 / 100
 27 ms 2508 KB 
//
// ~oisín~ C++ Template
//

#include                <bits/stdc++.h>
#define MX_N            5001
#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 22 ms 1484 KB Output is correct
2 Correct 27 ms 1496 KB Output is correct
3 Correct 23 ms 1548 KB Output is correct
4 Correct 23 ms 1524 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1484 KB Output is correct
2 Correct 27 ms 1496 KB Output is correct
3 Correct 23 ms 1548 KB Output is correct
4 Correct 23 ms 1524 KB Output is correct
5 Correct 4 ms 1868 KB Output is correct
6 Correct 5 ms 1868 KB Output is correct
7 Correct 4 ms 1868 KB Output is correct
8 Correct 5 ms 1868 KB Output is correct
9 Correct 5 ms 1868 KB Output is correct
10 Correct 5 ms 1800 KB Output is correct
11 Correct 5 ms 1868 KB Output is correct
12 Correct 5 ms 1868 KB Output is correct
13 Correct 5 ms 1868 KB Output is correct
14 Correct 5 ms 1868 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 2508 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1484 KB Output is correct
2 Correct 27 ms 1496 KB Output is correct
3 Correct 23 ms 1548 KB Output is correct
4 Correct 23 ms 1524 KB Output is correct
5 Correct 4 ms 1868 KB Output is correct
6 Correct 5 ms 1868 KB Output is correct
7 Correct 4 ms 1868 KB Output is correct
8 Correct 5 ms 1868 KB Output is correct
9 Correct 5 ms 1868 KB Output is correct
10 Correct 5 ms 1800 KB Output is correct
11 Correct 5 ms 1868 KB Output is correct
12 Correct 5 ms 1868 KB Output is correct
13 Correct 5 ms 1868 KB Output is correct
14 Correct 5 ms 1868 KB Output is correct
15 Runtime error 3 ms 2508 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -