제출 #1250443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1250443		akksss	Valley (BOI19_valley)	C++20	23 / 100	398 ms	84084 KiB

valley

#include "bits/stdc++.h"
using namespace std;
 
// For Ordered Set
 
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
// For snippet use pbds
 
#define pi 3.141592653589793238
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define int long long
 
ll M = 1000000007;
 
// Solution Starts Here.....

const int Log = 25;
const int NN = 2e5;
vector<int> adj[NN];
int level[NN];
int parent[NN][Log];
int sz[NN];
int tin[NN];
int counter = 0;
bool shops[NN];
int nearest[NN];
map<pair<int,int>, int> wt;
map<int,vector<int>> edges;
int weight[NN];
int mini[NN][Log];
void dfs(int u = 0, int p = -1){
    tin[u] = counter++;
    sz[u] = 1;
    for(auto v : adj[u]){
        if(v == p) continue;
        level[v] = level[u] + 1; 
        weight[v] = weight[u] + wt[{u, v}];
        parent[v][0] = u;
        for (int i = 1; i < Log; i++) {
            parent[v][i] = parent[parent[v][i-1]][i-1];
        }
        dfs(v, u);
        sz[u] += sz[v];
        nearest[u] = min(nearest[u], wt[{u, v}] + nearest[v]);
        if(nearest[u] == 1e18){
            mini[v][0] = 1e18;
        }
        else{
            mini[v][0] = nearest[u] - weight[u];
        }
        for (int i = 1; i < Log; i++) {
           mini[v][i] = min(mini[v][i-1], mini[parent[v][i-1]][i-1]); 
        }
    }
}

int lca(int u, int v){
    if(level[u] < level[v])  swap(u, v);
    for (int d = Log - 1; d >= 0; d--) {
        if (level[u] - (1 << d) >= level[v]) { u = parent[u][d]; }
    }
    if(u == v) return v;
    for (int i=Log-1; i >= 0; i--){
        if(parent[u][i] != parent[v][i]){
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return parent[u][0];
}


void solve(){
   int n, s, q, e; cin >> n >> s >> q >> e;
   e--;
   for (int i = 0; i < Log; i++) {
       parent[e][i] = e; 
       mini[e][i] = 1e18;
   }
   for (int i = 0; i < n-1; i++) {
       int u, v, w; cin >> u >> v >> w; 
       u--; v--;
       edges[i] = {u, v, w};
       adj[u].push_back(v);
       adj[v].push_back(u);
       wt[{u, v}] = w;
       wt[{v, u}] = w;
   }
   for (int i = 0; i < n; i++) {
       nearest[i] = 1e18; 
   }
   for (int i = 0; i < s; i++) {
      int c; cin >> c;
       shops[--c] = true;
       nearest[c] = 0;
   } 
  
   dfs(e, -1);
   
    
   auto distance = [&](int a, int b){
        int lc = lca(a, b);
        return weight[a] + weight[b] - 2*weight[lc];
   };
    

   while(q--){
       int i, r; cin >> i >> r;
       i--; r--;
       int u = edges[i][0]; 
       int v = edges[i][1];
       int w = edges[i][2];
       if(level[v] > level[u]) swap(u, v);
       if(distance(r, u) + w + distance(v, e) == distance(r, e)){
           int d = level[r] - level[u];
           int mn = 1e18;
           int tr = r;
           for (int j = 0; j < Log; j++) {
               if(d & (1<<j)){
                   mn = min(mini[tr][j], mn);
                   tr = parent[tr][j]; 
               } 
           }
           mn = min(nearest[tr] - weight[tr], mn);
           if(mn < 1e18){
                mn += weight[r];
           } 
           int ans = min(nearest[r], mn);
           if(ans < 1e18){
                cout << ans << "\n";
           }
           else cout << "oo\n";
       }
       else{
            cout << "escaped\n";
       }  

   } 
    
}
 
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1;
    // cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        solve();
    }
}

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