Submission #633077

#TimeUsernameProblemLanguageResultExecution timeMemory
633077a_aguiloValley (BOI19_valley)C++14
59 / 100
3073 ms30976 KiB
#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){ priority_queue<pair<long long int, pair<int, int>>> PQ; 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.top(); PQ.pop(); long long int dist = -1*act.first; int nodo = act.second.first; int padre = act.second.second; if(isShop[nodo]) return dist; 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({-1*(dist+(long long)w), {vecino, nodo}}); } } return -1; } 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 == -1) 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:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int e = 0; e < listaAdy[nodo].size(); ++e){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...