oj.uz

Submission #884668

# Submission time Handle Problem Language Result Execution time Memory
884668 2023-12-08T02:42:42 Z vijay72 Fountain (eJOI20_fountain) C++17
100 / 100
 134 ms 28644 KB 
#include "bits/stdc++.h"
using namespace std;

// clang-format off

using ll = long long;
#define sz(x) (int)x.size()

#ifdef DEBUG
    #include "debug.hpp"
#else
    #define dbg(x...) 0
#endif

// clang-format on
struct reservoir {
  int diameter;
  int capacity;
};

using Graph = std::vector<std::vector<int>>;
class Lift {
  // largest jump will be less than 2^max_pow
  int max_pow;
  // up[x][i] = 2^xth ansector of node x
  std::vector<std::vector<int>> up;
  std::vector<std::vector<int>> capacities;
  void dfs(const Graph &G, int cur_node, int par, vector<reservoir> &res) {
    up[0][cur_node] = par;
    for (auto child : G[cur_node]) {
      if (child == par) continue;

      capacities[0][child] = res[child].capacity;
      dfs(G, child, cur_node, res);
    }
  }

 public:
  Lift(const Graph &G, vector<reservoir> &res)
      : max_pow(31 - __builtin_clz(G.size()) + 1),
        up(max_pow, std::vector<int>(G.size(), -1)),
        capacities(max_pow, std::vector<int>(G.size(), INT_MAX)) {
    dfs(G, 0, -1, res);

    for (std::size_t x = 1; x < up.size(); x++) {
      for (std::size_t i = 1; i < G.size(); i++) {
        int mid = up[x - 1][i];
        if (mid != -1 && up[x - 1][mid] != -1) {
          up[x][i] = up[x - 1][mid];
          capacities[x][i] = capacities[x - 1][i] + capacities[x - 1][mid];
        }
      }
    }
  }

  int get_ans(int node, int water_poured) {
    for (int i = max_pow - 1; i >= 0; i--) {
      if (capacities[i][node] < water_poured) {
        water_poured -= capacities[i][node];
        node = up[i][node];
      }
    }
    return node;
  }
};

void solve() {
  int n, q;
  cin >> n >> q;

  vector<reservoir> reservoirs(n + 1);
  for (int i = 1; i <= n; i++)
    cin >> reservoirs[i].diameter >> reservoirs[i].capacity;

  Graph adj(n + 1);
  stack<int> st;
  for (int i = n; i >= 1; i--) {
    while (!st.empty() &&
           reservoirs[st.top()].diameter <= reservoirs[i].diameter)
      st.pop();

    if (st.empty()) {
      adj[0].push_back(i);
      adj[i].push_back(0);
    } else {
      adj[st.top()].push_back(i);
      adj[i].push_back(st.top());
    }
    st.push(i);
  }

  Lift l(adj, reservoirs);
  while (q--) {
    int node, water;
    cin >> node >> water;
    cout << l.get_ans(node, water) << "\n";
  }
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T = 1;
  while (T--) solve();
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 24544 KB Output is correct
2 Correct 109 ms 24380 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 93 ms 24544 KB Output is correct
9 Correct 109 ms 24380 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 52 ms 13684 KB Output is correct
12 Correct 134 ms 28644 KB Output is correct
13 Correct 120 ms 25544 KB Output is correct
14 Correct 81 ms 24520 KB Output is correct
15 Correct 73 ms 25204 KB Output is correct