oj.uz

답안 #884360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884360 2023-12-07T08:46:45 Z vijay72 Fountain (eJOI20_fountain) C++17
0 / 100
 223 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/4)) {
        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 && node; 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:27: warning: statement has no effect [-Wunused-value]
   10 |         #define dbg(x...) 0
      |                           ^
fountain.cpp:57:9: note: in expansion of macro 'dbg'
   57 |         dbg(capacity);
      |         ^~~
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:62:11: note: in expansion of macro 'dbg'
   62 |           dbg(i, node, capacity[i][node]);
      |           ^~~
fountain.cpp: In function 'void solve()':
fountain.cpp:10:27: warning: statement has no effect [-Wunused-value]
   10 |         #define dbg(x...) 0
      |                           ^
fountain.cpp:95:7: note: in expansion of macro 'dbg'
   95 |       dbg(adj);
      |       ^~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 223 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

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