Submission #633152

#	Time	Username	Problem	Language	Result	Execution time	Memory
633152		a_aguilo	Valley (BOI19_valley)	C++14	59 / 100	3075 ms	31040 KiB

valley

#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

vi isShop, padre, level;
vector<pair<int, int>> edges;
vvi listaAdy, weights, dp;
int N, Q, E, S, LG;

void dfs(int nodo){
    for (int e = 0; e < listaAdy[nodo].size(); ++e){
        int vecino = listaAdy[nodo][e];
        int dist = weights[nodo][e];
        if(padre[nodo] == vecino) continue;
        padre[vecino] = nodo;
        level[vecino] = level[nodo]+1;
        dfs(vecino);
    }
}

int KthAncestor(int nodo, int K){
    for(int i = LG-1; i >= 0; --i){
        if((1 << i)<= K){
            K^=(1 << i);
            nodo = dp[nodo][i];
        }
    }
    return nodo;
}

void preprocess(){
    dfs(E);
    dp = vvi(N, vi(LG));
    for(int i = 0; i < N; ++i){
        dp[i][0] = padre[i];
    }
    for(int h = 1; h < LG; ++h){
        for(int nodo = 0; nodo < N; ++nodo){
            dp[nodo][h] = dp[dp[nodo][h-1]][h-1];
        }
    }
}

int getSon (pair<int, int> p){
    int a = p.first;
    int b = p.second;
    if (a == padre[b]) return b;
    return a;
}

long long dijkstra(int origin, pair<int, int> take){
    queue<pair<long long int, pair<int, int>>> PQ;
    long long int ans = 1e18;
    int u = take.first; int v = take.second;
    PQ.push({0, {origin, -1}});
    while(!PQ.empty()){
        pair<long long int, pair<int, int>> act;
        act = PQ.front(); PQ.pop();
        long long int dist = act.first;
        int nodo = act.second.first;
        int padre = act.second.second;
        if(isShop[nodo]){
            ans = min(ans, dist);
            continue;
        }
        for(int e = 0; e < listaAdy[nodo].size(); ++e){
            int vecino = listaAdy[nodo][e];
            int w = weights[nodo][e];
            if((vecino == u and nodo == v) or (vecino == v and nodo == u)) continue;
            if(vecino == padre) continue;
            PQ.push({(dist+(long long)w), {vecino, nodo}});
        }
    }
    return ans;
}

int main(){
    cin >> N >> S >> Q >> E; E--;
    int a, b, w, I, R;
    LG = log2(N) + 2;
    listaAdy = vvi(N);
    weights = vvi(N);
    level = vi(N);
    padre = vi(N);
    padre[E] = E;
    level[E] = 0;
    isShop = vi(N, 0);
    for(int i = 1; i < N; ++i){
        cin >> a >> b >> w;
        a--; b--;
        edges.push_back({a, b});
        listaAdy[a].push_back(b);
        listaAdy[b].push_back(a);
        weights[a].push_back(w);
        weights[b].push_back(w);
    }
    for(int i = 0; i < S; ++i){
        cin >> a; a--;
        isShop[a] = 1;
    }
    preprocess();
    while(Q--){
        cin >> I >> R; I--; R--;
        int son = getSon(edges[I]);
        int d = level[R] - level[son];
        if(KthAncestor(R, d) != son){
            cout << "escaped" << endl;
            continue;
        }
        long long ans = dijkstra(R, edges[I]);
        if(ans == 1e18) cout << "oo" << endl;
        else cout << ans << endl;
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void dfs(int)':
valley.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for (int e = 0; e < listaAdy[nodo].size(); ++e){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:16:13: warning: unused variable 'dist' [-Wunused-variable]
   16 |         int dist = weights[nodo][e];
      |             ^~~~
valley.cpp: In function 'long long int dijkstra(int, std::pair<int, int>)':
valley.cpp:69:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int e = 0; e < listaAdy[nodo].size(); ++e){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41