제출 #884668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
884668		vijay72	Fountain (eJOI20_fountain)	C++17	100 / 100	134 ms	28644 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40