Submission #221797

#	Time	Username	Problem	Language	Result	Execution time	Memory
221797		patrikpavic2	Valley (BOI19_valley)	C++17	100 / 100	387 ms	68600 KiB

valley

/**
* 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 (stderr)

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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41