oj.uz

Submission #699914

# Submission time Handle Problem Language Result Execution time Memory
699914 2023-02-18T10:14:01 Z nima_aryan Valley (BOI19_valley) C++14
100 / 100
 347 ms 33388 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 10 ms 14292 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 10 ms 14292 KB Output is correct
5 Correct 7 ms 14036 KB Output is correct
6 Correct 8 ms 14036 KB Output is correct
7 Correct 7 ms 14188 KB Output is correct
8 Correct 8 ms 14028 KB Output is correct
9 Correct 8 ms 14036 KB Output is correct
10 Correct 8 ms 14164 KB Output is correct
11 Correct 9 ms 14156 KB Output is correct
12 Correct 8 ms 14036 KB Output is correct
13 Correct 8 ms 14164 KB Output is correct
14 Correct 8 ms 14188 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 21688 KB Output is correct
2 Correct 276 ms 21312 KB Output is correct
3 Correct 286 ms 21440 KB Output is correct
4 Correct 308 ms 25500 KB Output is correct
5 Correct 287 ms 24080 KB Output is correct
6 Correct 328 ms 33388 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 10 ms 14292 KB Output is correct
5 Correct 7 ms 14036 KB Output is correct
6 Correct 8 ms 14036 KB Output is correct
7 Correct 7 ms 14188 KB Output is correct
8 Correct 8 ms 14028 KB Output is correct
9 Correct 8 ms 14036 KB Output is correct
10 Correct 8 ms 14164 KB Output is correct
11 Correct 9 ms 14156 KB Output is correct
12 Correct 8 ms 14036 KB Output is correct
13 Correct 8 ms 14164 KB Output is correct
14 Correct 8 ms 14188 KB Output is correct
15 Correct 278 ms 21688 KB Output is correct
16 Correct 276 ms 21312 KB Output is correct
17 Correct 286 ms 21440 KB Output is correct
18 Correct 308 ms 25500 KB Output is correct
19 Correct 287 ms 24080 KB Output is correct
20 Correct 328 ms 33388 KB Output is correct
21 Correct 251 ms 21764 KB Output is correct
22 Correct 279 ms 21404 KB Output is correct
23 Correct 291 ms 21492 KB Output is correct
24 Correct 322 ms 24280 KB Output is correct
25 Correct 305 ms 31024 KB Output is correct
26 Correct 257 ms 21708 KB Output is correct
27 Correct 290 ms 21480 KB Output is correct
28 Correct 267 ms 21384 KB Output is correct
29 Correct 297 ms 25168 KB Output is correct
30 Correct 311 ms 28472 KB Output is correct
31 Correct 257 ms 21800 KB Output is correct
32 Correct 280 ms 21408 KB Output is correct
33 Correct 293 ms 21488 KB Output is correct
34 Correct 347 ms 24296 KB Output is correct
35 Correct 302 ms 29628 KB Output is correct
36 Correct 287 ms 25808 KB Output is correct