oj.uz

Submission #221797

# Submission time Handle Problem Language Result Execution time Memory
221797 2020-04-11T07:52:18 Z patrikpavic2 Valley (BOI19_valley) C++17
100 / 100
 387 ms 68600 KB 
/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  valley
* score: 100.0
* date:  2019-05-04 08:02:52.599602
*/
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, ll > pil;

const int N = 1e5 + 500;
const int LOG = 18;
const ll INF = 0x3f3f3f3f;

int par[N][LOG], ind[N], dep[N], A[N], B[N];
ll dis[N][LOG], dp2[N][LOG], dp[N];
int n, E, m, q;

vector < pil > v[N];
vector < ll > dp3[N], dp3_r[N];

ll f(int x,int lst){
    par[x][0] = lst; dp2[x][0] = INF * INF; dep[x] = dep[lst] + 1;
    ll cur = INF * INF;int koj = 0;
    for(pil y : v[x]){
        dp3[x].PB(dp[x]);
        if(y.X == lst) continue;
        ind[y.X] = koj++;
        dis[y.X][0] = y.Y;
        f(y.X, x);
        dp[x] = min(dp[x], dp[y.X] + y.Y);
    }
    reverse(v[x].begin(), v[x].end());
    for(pil y : v[x]){
        dp3_r[x].PB(dp[x]);
        if(y.X == lst) continue;
        cur = min(cur, dp[y.X] + y.Y);
    }
    reverse(dp3_r[x].begin(), dp3_r[x].end());
}

void napravi_sve_bitno(){
    // jos treba postaviti dp2[i][0] na sam parenta -- jesam
    for(int i = 1;i <= n;i++){
        dp2[i][0] = dis[i][0] + min(dp3[par[i][0]][ind[i]], dp3_r[par[i][0]][ind[i]]);
    }
    for(int k = 1;k < LOG;k++){
        for(int i = 1;i <= n;i++){
            par[i][k] = par[par[i][k - 1]][k - 1];
            dis[i][k] = dis[i][k - 1] + dis[par[i][k - 1]][k - 1];
            dp2[i][k] = min(dp2[i][k - 1], dis[i][k - 1] + dp2[par[i][k - 1]][k - 1]);
            //dp2[i][k] = min(dp2[i][k], min(dp3[par[par[i][k - 1]][0]][ind[par[i][k - 1]]], dp3_r[par[par[i][k - 1]][0]][ind[par[i][k - 1]]])); -- mislim da ovo ne treba
        }
    }
}

bool nalazi(int x,int y){
    if(dep[y] > dep[x]) return 0;
    for(int i = LOG - 1;i >= 0;i--){
        if(dep[x] - (1 << i) >= dep[y])
            x = par[x][i];
    }
    return x == y;
}

ll nadi(int x,int y){
    ll ret = dp[x], cur_d = 0;
    //printf("NADI %d i %d DP %lld\n", x, y, dp[x]);
    for(int i = LOG - 1;i >= 0;i--){
        if(dep[x] - (1 << i) >= dep[y]){
            ret = min(ret, cur_d + dp2[x][i]);
            cur_d += dis[x][i];
            x = par[x][i];
        }
    }
    return ret;
}

int main(){
    scanf("%d%d%d%d", &n, &m, &q, &E);
    for(int i = 1;i < n;i++){
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        v[x].PB({y, z});
        v[y].PB({x, z});
        A[i] = x, B[i] = y;
        dp[i] = INF * INF;
    }
    dp[n] = INF * INF;
    for(int i = 0;i < m;i++){
        int x; scanf("%d", &x); dp[x] = 0;
    }
    f(E, E);
    //return 0;
    napravi_sve_bitno();

    for(int i = 0;i < q;i++){
        int x, y; scanf("%d%d", &x, &y);
        if(dep[A[x]] < dep[B[x]]) swap(A[x], B[x]);
        if(!nalazi(y, A[x]) || !nalazi(y, B[x])){
            printf("escaped\n"); continue;
        }
        ll ans = nadi(y, A[x]);
        if(ans >= INF * INF) printf("oo\n");
        else printf("%lld\n", ans);
    }
}

Compilation message

valley.cpp: In function 'll f(int, int)':
valley.cpp:52:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
valley.cpp: In function 'int main()':
valley.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &m, &q, &E);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:94:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y, z; scanf("%d%d%d", &x, &y, &z);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:102:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x; scanf("%d", &x); dp[x] = 0;
                ~~~~~^~~~~~~~~~
valley.cpp:109:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y; scanf("%d%d", &x, &y);
                   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7680 KB Output is correct
2 Correct 12 ms 7680 KB Output is correct
3 Correct 12 ms 7680 KB Output is correct
4 Correct 13 ms 7680 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7680 KB Output is correct
2 Correct 12 ms 7680 KB Output is correct
3 Correct 12 ms 7680 KB Output is correct
4 Correct 13 ms 7680 KB Output is correct
5 Correct 10 ms 8064 KB Output is correct
6 Correct 10 ms 7936 KB Output is correct
7 Correct 10 ms 8064 KB Output is correct
8 Correct 10 ms 7936 KB Output is correct
9 Correct 10 ms 7928 KB Output is correct
10 Correct 10 ms 7936 KB Output is correct
11 Correct 11 ms 8064 KB Output is correct
12 Correct 10 ms 7936 KB Output is correct
13 Correct 10 ms 7936 KB Output is correct
14 Correct 10 ms 8056 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 62840 KB Output is correct
2 Correct 310 ms 61944 KB Output is correct
3 Correct 309 ms 61688 KB Output is correct
4 Correct 341 ms 64504 KB Output is correct
5 Correct 329 ms 64520 KB Output is correct
6 Correct 387 ms 67576 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7680 KB Output is correct
2 Correct 12 ms 7680 KB Output is correct
3 Correct 12 ms 7680 KB Output is correct
4 Correct 13 ms 7680 KB Output is correct
5 Correct 10 ms 8064 KB Output is correct
6 Correct 10 ms 7936 KB Output is correct
7 Correct 10 ms 8064 KB Output is correct
8 Correct 10 ms 7936 KB Output is correct
9 Correct 10 ms 7928 KB Output is correct
10 Correct 10 ms 7936 KB Output is correct
11 Correct 11 ms 8064 KB Output is correct
12 Correct 10 ms 7936 KB Output is correct
13 Correct 10 ms 7936 KB Output is correct
14 Correct 10 ms 8056 KB Output is correct
15 Correct 276 ms 62840 KB Output is correct
16 Correct 310 ms 61944 KB Output is correct
17 Correct 309 ms 61688 KB Output is correct
18 Correct 341 ms 64504 KB Output is correct
19 Correct 329 ms 64520 KB Output is correct
20 Correct 387 ms 67576 KB Output is correct
21 Correct 256 ms 62332 KB Output is correct
22 Correct 282 ms 61432 KB Output is correct
23 Correct 318 ms 61304 KB Output is correct
24 Correct 325 ms 64376 KB Output is correct
25 Correct 355 ms 68600 KB Output is correct
26 Correct 259 ms 62328 KB Output is correct
27 Correct 274 ms 61688 KB Output is correct
28 Correct 285 ms 61180 KB Output is correct
29 Correct 325 ms 63352 KB Output is correct
30 Correct 364 ms 65400 KB Output is correct
31 Correct 264 ms 62508 KB Output is correct
32 Correct 274 ms 61560 KB Output is correct
33 Correct 305 ms 61304 KB Output is correct
34 Correct 339 ms 64252 KB Output is correct
35 Correct 368 ms 68424 KB Output is correct
36 Correct 348 ms 65028 KB Output is correct