Submission #825633

#	Time	Username	Problem	Language	Result	Execution time	Memory
825633		Shreyan_Paliwal	Valley (BOI19_valley)	C++17	100 / 100	370 ms	46236 KiB

valley

// // #pragma GCC optimize("Ofast")
// // #include <bits/stdc++.h>
// // using namespace std;

// // #define int long long

// // const int maxn = 100000;
// // const int INF = 2000000000;

// // int n, s, q, e; // nodes, numshops, numqueries, valleynode
// // vector<pair<int,int>> adj[maxn];
// // pair<int,int> edges[maxn];
// // int shop[maxn]; // is shop?
// // int closest[maxn]; // closest shop in subtree

// // int dist[maxn]; // distance to root, set


// // int dpth[maxn]; // depth from root, set
// // int bl[maxn][20]; // set
// // int bld[maxn][20]; // array[nd] = - 2 * dist[nd] + min(dist[shop]) for shop in subtree[dist]


// // void dfs(int nd, int par, int pardist, int d) {
// //     // set depth
// //     dpth[nd] = d;

// //     // set binary lifting
// //     bl[nd][0] = par;
// //     for (int i = 1; i < 20; i++) bl[nd][i] = bl[bl[nd][i-1]][i-1];

// //     // recurse dfs, set distance from root
// //     for (auto i : adj[nd])
// //         if (i.first != par) {
// //             dist[i.first] = dist[nd] + i.second;    
// //             dfs(i.first, nd, i.second, d+1);
// //         }
    
// //     // init closest shop in subtree
// //     closest[nd] = shop[nd] ? 0 : INF;   
// //     for (auto i : adj[nd])
// //         if (i.first != par)
// //             closest[nd] = min(closest[nd], i.second + closest[i.first]);

// //     return;
// // }

// // void dfs_bld(int nd) {
// //     if (closest[nd] == INF) bld[nd][0] = INF;
// //     else bld[nd][0] = -dist[nd] + closest[nd];
// //     for (int i = 1; i < 20; i++) bld[nd][i] = min(bld[nd][i-1], bld[bl[nd][i-1]][i-1]);

// //     for (auto i : adj[nd])
// //         if (i.first != bl[nd][0])
// //             dfs_bld(i.first);
// // }

// // inline int jmp(int nd, int k) {
// //     for (int i = 19; i >= 0; i--) if ((k >> i) & 1) nd = bl[nd][i];
// //     return nd;
// // }

// // inline bool on_path(int nd, int nd2) {
// //     // checking if nd2 is on nd's path to root
// //     return (dpth[nd] >= dpth[nd2] && jmp(nd, dpth[nd] - dpth[nd2]) == nd2);
// // }

// // void solve() {
// //     cin >> n >> s >> q >> e; e--;
// //     for (int i = 0; i < n-1; i++) {
// //         int c; cin >> edges[i].first >> edges[i].second >> c;
// //         edges[i].first--, edges[i].second--;
// //         adj[edges[i].first].push_back({edges[i].second, c});
// //         adj[edges[i].second].push_back({edges[i].first, c});
// //     }

// //     for (int i = 0; i < s; i++) { int a; cin >> a; a--; shop[a] = 1; }

// //     dfs(e, e, 0, 0);
// //     dfs_bld(e);

// //     for (int i = 0; i < q; i++) {
// //         // a is a removed, b is b to find
// //         int a, b; cin >> a >> b; a--, b--;

// //         if (dpth[edges[a].first] < dpth[edges[a].second]) 
// //             swap(edges[a].first, edges[a].second);

// //         // check if escape possible
// //         if (!on_path(b, edges[a].first)) {
// //             cout << "escaped" << endl;
// //             continue;
// //         }

// //         // not possible, so search
// //         int val = INF;
// //         int B = b;
// //         for (int i = 19; i >= 0; i--) 
// //             if (((dpth[edges[a].first] - dpth[b] + 1) >> i) & 1)
// //                 val = min(val, bld[b][i]), 
// //                 b = bl[b][i];

// //         if (val == INF) {
// //             cout << "oo" << endl;
// //             continue;
// //         }

// //         cout << val + dist[B] << endl;
// //         continue;
// //     }

// // }

// // signed main() {
// //     cin.tie(nullptr) -> ios::sync_with_stdio(false);
// //     // freopen("main.in", "r", stdin);
// //     int t; 
// //     // cin >> t;
// //     t=1;
// //     while(t--) solve();
// //     return 0;
// // }

// #include <bits/stdc++.h>
// using namespace std;

// #define int long long

// const int maxn = 200000;
// const int INF = 1ll << 60;

// int n, s, q, e;

// vector<pair<int,int>> adj[maxn];
// pair<int,int> edges[maxn];

// int dist[maxn];
// int dpth[maxn];
// int closest[maxn];
// int shop[maxn];

// int bl[maxn][20];
// int bld[maxn][20];

// int st[maxn], en[maxn], cur = 0;

// void dfs(int nd, int par, int d) {
//     st[nd] = cur++;
//     dist[nd] = dist[par] + d;
//     dpth[nd] = dpth[par] + 1;

//     for (auto i : adj[nd])
//         if (i.first != par)
//             dfs(i.first, nd, i.second);

//     closest[nd] = (shop[nd] ? dist[nd] : INF);
//     for (auto i : adj[nd])
//         if (i.first != par && closest[i.first] != INF)
//             closest[nd] = min(closest[nd], closest[i.first]);
    
//     en[nd] = cur++;
// }

// void dfs_bl(int nd, int par) {
//     bl[nd][0] = par;
//     bld[nd][0] = (closest[nd] == INF ? INF : closest[nd] - 2 * dist[nd]);

//     for (int i = 1; i < 20; i++) bl[nd][i] = bl[bl[nd][i-1]][i-1];
//     for (int i = 1; i < 20; i++) bld[nd][i] = min(bld[nd][i-1], bld[bl[nd][i-1]][i-1]);

//     for (auto i : adj[nd])
//         if (i.first != par)
//             dfs_bl(i.first, nd);
// }

// signed main() {
//     // freopen("main.in", "r", stdin);

//     cin >> n >> s >> q >> e; e--;

//     for (int i = 0; i < n-1; i++) {
//         int a, b, c; cin >> a >> b >> c; a--, b--;
//         adj[a].push_back({b, c});
//         adj[b].push_back({a, c});
//         edges[i] = make_pair(b, c);
//     }

//     for (int i = 0; i < s; i++) {
//         int a; cin >> a; a--;
//         shop[a] = 1;
//     }

//     dfs(e, e, 0);
//     dfs_bl(e, e);

//     for (int i = 0; i < n-1; i++)
//         if (dpth[edges[i].first] < dpth[edges[i].second])
//             swap(edges[i].first, edges[i].second);

//     for (int i = 0; i < q; i++) {
//         int a, b; cin >> a >> b; a--, b--;
//         // if (dpth[edges[a].first] < dpth[edges[a].second]) swap(edges[a].first, edges[a].second);

//         // can escape?
//         if (!(st[edges[a].first] <= st[b] && en[b] <= en[edges[a].first])) {
//             cout << "escaped" << endl;
//             continue;
//         }

//         int cost = INF;
//         int nd = b;
//         for (int i = 19; i >= 0; i--)
//             if (((dpth[b] - dpth[edges[a].first]) >> i) & 1)
//                 cost = min(cost, bld[nd][i]), 
//                 nd = bl[nd][i];
//         cost = min(cost, bld[nd][0]);

//         if (cost == INF) { cout << "oo" << endl; continue; }

//         cout << cost + dist[b] << endl;
//         continue;
//     }

//     return 0;
// }

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 200005;
const int maxlg = 20;
const ll inf = 1LL << 60;

vector<pair<int, ll>> adj [maxn];
ll height [maxn];
int lvl [maxn];
ll dp [maxn];
bool store [maxn];
int start_time [maxn];
int end_time [maxn];
int cur_time;

void build_dp (int vertex, int parent, ll cur_height) {
  cur_time++;
  start_time[vertex] = cur_time;
  
  height[vertex] = cur_height;
  lvl[vertex] = lvl[parent] + 1;
  for (pair<int, ll> nxt : adj[vertex]) {
    if (nxt.first != parent) {
      build_dp(nxt.first, vertex, cur_height + nxt.second);
    }
  }

  if (store[vertex]) {
    dp[vertex] = height[vertex];
  } else {
    dp[vertex] = inf;
    for (pair<int, ll> nxt : adj[vertex]) {
      if (nxt.first != parent) {
        dp[vertex] = min(dp[vertex], dp[nxt.first]);
      }
    }
  }

  end_time[vertex] = cur_time;
}

bool is_parent (int u, int par) {
  return start_time[par] <= start_time[u] && end_time[u] <= end_time[par];
}

int jmp [maxn][maxlg];
ll ans_jmp [maxn][maxlg];

void build_jmp (int vertex, int parent) {
  jmp[vertex][0] = parent;
  if (dp[vertex] == inf) {
    ans_jmp[vertex][0] = inf;
  } else {
    ans_jmp[vertex][0] = dp[vertex] - 2 * height[vertex];
  }

  for (int i = 1; i < maxlg; i++) {
    jmp[vertex][i] = jmp[jmp[vertex][i - 1]][i - 1];
    ans_jmp[vertex][i] = min(ans_jmp[vertex][i - 1], ans_jmp[jmp[vertex][i - 1]][i - 1]);
  }

  for (pair<int, ll> nxt : adj[vertex]) {
    if (nxt.first != parent) {
      build_jmp(nxt.first, vertex);
    }
  }
}

ll query (int vertex, int forb) {
  if (!is_parent(vertex, forb)) {
    return -1;
  }

  ll cur_h = height[vertex];
  
  int diff = lvl[vertex] - lvl[forb];
  ll ans = inf;
  for (int i = maxlg - 1; i >= 0; i--) {
    if (diff & 1 << i) {
      ans = min(ans, ans_jmp[vertex][i]);
      vertex = jmp[vertex][i];
    }
  }
  ans = min(ans, ans_jmp[vertex][0]);

  if (ans != inf) {
    ans += cur_h;
  }
  
  return ans;
}

int main () {
  int vertexc, storec, queryc, root;
  cin >> vertexc >> storec >> queryc >> root;

  vector<pair<int, int>> edges;
  for (int i = 0; i < vertexc - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;

    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
    edges.push_back(make_pair(u, v));
  }

  for (int i = 0; i < storec; i++) {
    int x;
    cin >> x;
    store[x] = true;
  }

  build_dp(root, root, 0);
  build_jmp(root, root);
  
  for (int i = 0; i < vertexc - 1; i++) {
    if (lvl[edges[i].first] < lvl[edges[i].second]) {
      swap(edges[i].first, edges[i].second);
    }
  }
  
  for (int i = 0; i < queryc; i++) {
    int forb_id, cur_vertex;
    cin >> forb_id >> cur_vertex;

    ll ans = query(cur_vertex, edges[forb_id - 1].first);
    if (ans == -1) {
      cout << "escaped" << '\n';
    } else if (ans == inf) {
      cout << "oo" << '\n';
    } else {
      cout << ans << '\n';
    }
  }
}

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