oj.uz

Submission #291122

# Submission time Handle Problem Language Result Execution time Memory
291122 2020-09-04T17:27:54 Z alexandra_udristoiu Valley (BOI19_valley) C++14
100 / 100
 795 ms 49400 KB 
#include<iostream>
#include<vector>
#define DIM 100005
#define INF 1000000000000000LL
#define f first
#define s second
using namespace std;
int n, k, i, q, x, y, ii, c, rad, nod;
int niv[DIM], a[18][DIM], sh[DIM], b[DIM];
long long d[DIM], d2[18][DIM], sum[18][DIM], sol, tot;
pair<int, int> w[DIM];
vector< pair<int, int> > v[DIM];
void dfs(int nod, int t){
    d[nod] = INF;
    if(sh[nod] == 1){
        d[nod] = 0;
    }
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i].f;
        if(vecin != t){
            a[0][vecin] = nod;
            sum[0][vecin] = v[nod][i].s;
            niv[vecin] = 1 + niv[nod];
            dfs(vecin, nod);
            d[nod] = min(d[nod], d[vecin] + v[nod][i].s);
        }
    }
}
int main(){
    cin>> n >> k >> q >> rad;
    for(i = 1; i < n; i++){
        cin>> x >> y >> c;
        w[i] = make_pair(x, y);
        v[x].push_back( make_pair(y, c) );
        v[y].push_back( make_pair(x, c) );
    }
    for(i = 1; i <= k; i++){
        cin>> x;
        sh[x] = 1;
    }
    dfs(rad, 0);
    for(i = 1; i <= n; i++){
        d2[0][i] = sum[0][i] + d[ a[0][i] ];
    }
    for(ii = 1; (1 << ii) < n; ii++){
        for(i = 1; i <= n; i++){
            a[ii][i] = a[ii - 1][ a[ii - 1][i] ];
            if(a[ii][i] != 0){
                sum[ii][i] = sum[ii - 1][i] + sum[ii - 1][ a[ii - 1][i] ];
                d2[ii][i] = min(d2[ii - 1][i], sum[ii - 1][i] + d2[ii - 1][ a[ii - 1][i] ]);
            }
        }
    }
    for(i = 2; i <= n; i++){
        b[i] = 1 + b[i / 2];
    }
    for(; q; q--){
        cin>> ii >> x;
        if(niv[ w[ii].f ] > niv[ w[ii].s ]){
            y = w[ii].f;
        }
        else{
            y = w[ii].s;
        }
        ii = niv[x] - niv[y];
        nod = x;
        while(ii > 0){
            nod = a[ b[ii] ][nod];
            ii -= (1 << b[ii]);
        }
        if(nod != y){
            cout<<"escaped\n";
            continue;
        }
        sol = d[x];
        nod = x;
        tot = 0;
        ii = niv[x] - niv[y];
        while(ii != 0){
            sol = min(sol, tot + d2[ b[ii] ][nod]);
            tot += sum[ b[ii] ][nod];
            nod = a[ b[ii] ][nod];
            ii -= (1 << b[ii]);
        }
        if(sol >= INF){
            cout<<"oo\n";
        }
        else{
            cout<< sol <<"\n";
        }
    }
}

Compilation message

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2936 KB Output is correct
2 Correct 32 ms 2944 KB Output is correct
3 Correct 32 ms 3072 KB Output is correct
4 Correct 31 ms 3000 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2936 KB Output is correct
2 Correct 32 ms 2944 KB Output is correct
3 Correct 32 ms 3072 KB Output is correct
4 Correct 31 ms 3000 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 7 ms 3072 KB Output is correct
8 Correct 8 ms 2944 KB Output is correct
9 Correct 7 ms 3072 KB Output is correct
10 Correct 7 ms 3072 KB Output is correct
11 Correct 8 ms 2944 KB Output is correct
12 Correct 8 ms 3072 KB Output is correct
13 Correct 8 ms 3072 KB Output is correct
14 Correct 7 ms 3200 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 22972 KB Output is correct
2 Correct 668 ms 24568 KB Output is correct
3 Correct 721 ms 31900 KB Output is correct
4 Correct 731 ms 41720 KB Output is correct
5 Correct 744 ms 41680 KB Output is correct
6 Correct 795 ms 45048 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2936 KB Output is correct
2 Correct 32 ms 2944 KB Output is correct
3 Correct 32 ms 3072 KB Output is correct
4 Correct 31 ms 3000 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 7 ms 3072 KB Output is correct
8 Correct 8 ms 2944 KB Output is correct
9 Correct 7 ms 3072 KB Output is correct
10 Correct 7 ms 3072 KB Output is correct
11 Correct 8 ms 2944 KB Output is correct
12 Correct 8 ms 3072 KB Output is correct
13 Correct 8 ms 3072 KB Output is correct
14 Correct 7 ms 3200 KB Output is correct
15 Correct 665 ms 22972 KB Output is correct
16 Correct 668 ms 24568 KB Output is correct
17 Correct 721 ms 31900 KB Output is correct
18 Correct 731 ms 41720 KB Output is correct
19 Correct 744 ms 41680 KB Output is correct
20 Correct 795 ms 45048 KB Output is correct
21 Correct 606 ms 25824 KB Output is correct
22 Correct 605 ms 27640 KB Output is correct
23 Correct 635 ms 33400 KB Output is correct
24 Correct 670 ms 44664 KB Output is correct
25 Correct 738 ms 49344 KB Output is correct
26 Correct 587 ms 26104 KB Output is correct
27 Correct 615 ms 27360 KB Output is correct
28 Correct 633 ms 33612 KB Output is correct
29 Correct 675 ms 44280 KB Output is correct
30 Correct 735 ms 47352 KB Output is correct
31 Correct 629 ms 26488 KB Output is correct
32 Correct 617 ms 27760 KB Output is correct
33 Correct 636 ms 35448 KB Output is correct
34 Correct 679 ms 45060 KB Output is correct
35 Correct 739 ms 49400 KB Output is correct
36 Correct 646 ms 45176 KB Output is correct