oj.uz

Submission #884419

# Submission time Handle Problem Language Result Execution time Memory
884419 2023-12-07T10:15:42 Z vijay72 Fountain (eJOI20_fountain) C++17
0 / 100
 219 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(), 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:27: warning: statement has no effect [-Wunused-value]
   10 |         #define dbg(x...) 0
      |                           ^
fountain.cpp:65:13: note: in expansion of macro 'dbg'
   65 |             dbg(node);
      |             ^~~
fountain.cpp:10:27: warning: statement has no effect [-Wunused-value]
   10 |         #define dbg(x...) 0
      |                           ^
fountain.cpp:67:13: note: in expansion of macro 'dbg'
   67 |             dbg(node);
      |             ^~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 3 ms 1156 KB Output is correct
5 Incorrect 10 ms 16220 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 219 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 3 ms 1156 KB Output is correct
5 Incorrect 10 ms 16220 KB Output isn't correct
6 Halted 0 ms 0 KB -