oj.uz

Submission #884741

# Submission time Handle Problem Language Result Execution time Memory
884741 2023-12-08T10:18:43 Z vijay72 Fountain (eJOI20_fountain) C++17
30 / 100
 318 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()) + 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:31: warning: statement has no effect [-Wunused-value]
   10 |             #define dbg(x...) 0
      |                               ^
fountain.cpp:65:17: note: in expansion of macro 'dbg'
   65 |                 dbg(node);
      |                 ^~~
fountain.cpp:10:31: warning: statement has no effect [-Wunused-value]
   10 |             #define dbg(x...) 0
      |                               ^
fountain.cpp:67:17: 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 1 ms 840 KB Output is correct
3 Correct 2 ms 832 KB Output is correct
4 Correct 3 ms 1120 KB Output is correct
5 Correct 10 ms 16476 KB Output is correct
6 Correct 4 ms 6084 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 318 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 348 KB Output is correct
2 Correct 1 ms 840 KB Output is correct
3 Correct 2 ms 832 KB Output is correct
4 Correct 3 ms 1120 KB Output is correct
5 Correct 10 ms 16476 KB Output is correct
6 Correct 4 ms 6084 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Runtime error 318 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -