oj.uz

답안 #884356

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884356 2023-12-07T08:44:40 Z vijay72 Fountain (eJOI20_fountain) C++17
0 / 100
 230 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;

// clang-format off
using ll = long long;

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

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

using Graph = std::vector<std::vector<int>>;
class LCA {
  // 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;

  // capacity[x][i] -> sum of capacities from i till 2^ith ancestor but NOT
  // INCLUDING capacity of ancestor
  std::vector<std::vector<ll>> capacity;

  void dfs(const Graph &G, int cur_node, int par,
           vector<reservoir> reservoir_list) {
    up[0][cur_node] = par;

    for (auto child : G[cur_node]) {
      if (child == par) continue;

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

 public:
  LCA(const Graph &G, vector<reservoir> reservoir_list)
      : max_pow(31 - __builtin_clz(G.size())),
        up(max_pow, std::vector<int>(G.size(), -1)),
        capacity(max_pow, vector<ll>(G.size(), LONG_LONG_MAX/2)) {
    dfs(G, 0, -1, reservoir_list);

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

  int query(int node, ll water_poured) const {
    for (int i = max_pow - 1; i >= 0; i--) {
      dbg(i, node, capacity[i][node]);
      if (capacity[i][node] < water_poured) {
        water_poured -= capacity[i][node];
        node = up[i][node];
      }
    }
    return node;
  }
};

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

  Graph adj(n + 1);
  vector<reservoir> reservoir_list(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> reservoir_list[i].diameter >> reservoir_list[i].capacity;
  }

  stack<pair<int, int>> st;
  for (int i = n; i >= 1; i--) {
    while (!st.empty() && st.top().first < reservoir_list[i].diameter) st.pop();

    if (st.empty()) {
      adj[0].push_back(i);
      adj[i].push_back(0);
    } else {
      adj[st.top().second].push_back(i);
      adj[i].push_back(st.top().second);
    }
    st.push({reservoir_list[i].diameter, i});
  }
  dbg(adj);
  LCA l(adj, reservoir_list);

  while (q--) {
    int node;
    ll water_poured;
    cin >> node >> water_poured;
    cout << l.query(node, water_poured) << "\n";
  }
}

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

Compilation message

fountain.cpp: In constructor 'LCA::LCA(const Graph&, std::vector<reservoir>)':
fountain.cpp:10:23: warning: statement has no effect [-Wunused-value]
   10 |     #define dbg(x...) 0
      |                       ^
fountain.cpp:57:5: note: in expansion of macro 'dbg'
   57 |     dbg(capacity);
      |     ^~~
fountain.cpp: In member function 'int LCA::query(int, ll) const':
fountain.cpp:10:23: warning: statement has no effect [-Wunused-value]
   10 |     #define dbg(x...) 0
      |                       ^
fountain.cpp:62:7: note: in expansion of macro 'dbg'
   62 |       dbg(i, node, capacity[i][node]);
      |       ^~~
fountain.cpp: In function 'void solve()':
fountain.cpp:10:23: warning: statement has no effect [-Wunused-value]
   10 |     #define dbg(x...) 0
      |                       ^
fountain.cpp:95:3: note: in expansion of macro 'dbg'
   95 |   dbg(adj);
      |   ^~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 230 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 844 KB Output isn't correct
3 Halted 0 ms 0 KB -