oj.uz

Submission #884743

# Submission time Handle Problem Language Result Execution time Memory
884743 2023-12-08T10:20:20 Z vijay72 Fountain (eJOI20_fountain) C++17
100 / 100
 267 ms 36052 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()) + 1),
        up(max_pow, std::vector<int>(G.size(), -1)),
        capacity(max_pow, vector<ll>(G.size(), INT_MAX)) {
    dfs(G, 0, -1, reservoir_list);

    for (std::size_t x = 1; x < up.size(); x++) {
      for (std::size_t i = 1; 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];
        }
      }
    }
  }

  int query(int node, ll water_poured) const {
    for (int i = max_pow - 1; i >= 0 && node; i--) {
      if (capacity[i][node] < water_poured) {
        water_poured -= capacity[i][node];
        dbg(node);
        node = up[i][node];
        dbg(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});
  }

  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 member function 'int LCA::query(int, ll) const':
fountain.cpp:10:35: warning: statement has no effect [-Wunused-value]
   10 |                 #define dbg(x...) 0
      |                                   ^
fountain.cpp:65:9: note: in expansion of macro 'dbg'
   65 |         dbg(node);
      |         ^~~
fountain.cpp:10:35: warning: statement has no effect [-Wunused-value]
   10 |                 #define dbg(x...) 0
      |                                   ^
fountain.cpp:67:9: note: in expansion of macro 'dbg'
   67 |         dbg(node);
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 33012 KB Output is correct
2 Correct 135 ms 30888 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 0 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 604 KB Output is correct
8 Correct 146 ms 33012 KB Output is correct
9 Correct 135 ms 30888 KB Output is correct
10 Correct 1 ms 536 KB Output is correct
11 Correct 57 ms 17344 KB Output is correct
12 Correct 267 ms 36052 KB Output is correct
13 Correct 137 ms 32688 KB Output is correct
14 Correct 110 ms 31456 KB Output is correct
15 Correct 103 ms 32216 KB Output is correct