Submission #699914

#	Time	Username	Problem	Language	Result	Execution time	Memory
699914		nima_aryan	Valley (BOI19_valley)	C++14	100 / 100	347 ms	33388 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

const i64 inf = 1e15;
const int maxn = 1e5 + 10;

template<class Fun>
class y_combinator_result {
   Fun fun_;
public:
   template<class T>
   explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

   template<class ...Args>
   decltype(auto) operator()(Args &&...args) {
      return fun_(std::ref(*this), std::forward<Args>(args)...);
   }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
   return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int n, s, q, e;
   cin >> n >> s >> q >> e;
   vector<vector<pair<int, int>>> adj(maxn);
   vector<int> from(maxn), to(maxn), cost(maxn);
   for (int i = 1; i <= n - 1; ++i) {
      cin >> from[i] >> to[i] >> cost[i];
      adj[from[i]].emplace_back(to[i], cost[i]);
      adj[to[i]].emplace_back(from[i], cost[i]);
   }
   vector<bool> shop(maxn);
   for (int i = 0; i < s; ++i) {
      int x;
      cin >> x;
      shop[x] = true;
   }
   vector<vector<pair<int, int>>> query(maxn);
   for (int i = 0; i < q; ++i) {
      int a, b;
      cin >> a >> b;
      query[b].emplace_back(a, i);
   }
   vector<i64> tree(4 * maxn);
   vector<i64> lazy(4 * maxn);
   auto prop = [&](int node, int l, int r) -> void {
      tree[node] += lazy[node];
      if (l != r) {
         lazy[node << 1] += lazy[node];
         lazy[node << 1 | 1] += lazy[node];
      }
      lazy[node] = 0;
   };
   auto update = y_combinator([&](auto self, int node, int l, int r, int fromx, int tox, i64 val) -> void {
      prop(node, l, r);
      if (fromx > r || tox < l) {
         return;
      }
      if (l >= fromx && r <= tox) {
         lazy[node] += val;
         prop(node, l, r);
         return;
      }
      int mid = (l + r) >> 1;
      self(node << 1, l, mid, fromx, tox, val);
      self(node << 1 | 1, mid + 1, r, fromx, tox, val);
      tree[node] = min(tree[node << 1], tree[node << 1 | 1]);
   });
   auto ask = y_combinator([&](auto self, int node, int l, int r, int fromx, int tox) -> i64 {
      prop(node , l , r) ;
      if (fromx > r || tox < l || fromx > tox) {
         return inf;
      }
      if (l >= fromx && r <= tox) {
         return tree[node];
      }
      int mid = (l + r) >> 1;
      i64 a = self(node << 1, l, mid, fromx , tox);
      i64 b = self(node << 1 | 1, mid + 1, r, fromx, tox);
      return min(a, b);
   });
   vector<int> in(maxn), out(maxn);
   int timer = 0;
   auto dfs1 = y_combinator([&](auto self, int node, int parent, i64 dist) -> void {
      in[node] = ++timer;
      if (shop[node]) {
         update(1, 1, n, in[node], in[node], dist);
      }
      else {
         update(1, 1, n, in[node], in[node], inf);
      }
      for (auto& child : adj[node]) {
         if (child.first == parent) {
            continue;
         }
         self(child.first, node, dist + child.second);
      }
      out[node] = timer;
   });
   dfs1(1, -1, 0);
   for (int i = 1; i <= n - 1; ++i) {
      if (in[to[i]] < in[from[i]]) {
         swap(to[i], from[i]);
      }
   }
   vector<i64> ans(maxn);
   auto dfs2 = y_combinator([&](auto self, int node, int parent) -> void {
      for (auto& qu : query[node]) {
         int x = qu.first;
         bool flag1 = (in[node] >= in[to[x]] && in[node] <= out[to[x]]);
         bool flag2 = (in[e] >= in[to[x]] && in[e] <= out[to[x]]) ;
         if (flag1 == flag2) {
            ans[qu.second] = -2;
            continue;
         }
         if (flag1) {
            ans[qu.second] = ask(1, 1, n, in[to[x]], out[to[x]]) ;
            if (ans[qu.second] > 1e14) {
               ans[qu.second] = -1;
            }
         }
         else {
            i64 a = ask(1, 1, n, 1, in[to[x]] - 1);
            i64 b = ask(1, 1, n, out[to[x]] + 1, n);
            ans[qu.second] = min(a, b);
            if (ans[qu.second] > 1e14) {
               ans[qu.second] = -1;
            }
         }
      }
      for (auto& child : adj[node]) {
         if (child.first == parent) {
            continue;
         }
         update(1, 1, n, 1, n, child.second);
         update(1, 1, n, in[child.first], out[child.first], -2ll * child.second);
         self(child.first, node);
         update(1, 1, n, 1, n, -1ll * child.second);
         update(1, 1, n, in[child.first], out[child.first], 2ll * child.second);
      }
   });
   dfs2(1, -1);
   for (int i = 0; i < q; ++i) {
      if (ans[i] >= 0) {
         cout << ans[i] << '\n';
      }
      else if (ans[i] == -1) {
         cout << "oo" << '\n';
      }
      else {
         cout << "escaped" << '\n';
      }
   }
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

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