Submission #1036505

#TimeUsernameProblemLanguageResultExecution timeMemory
10365050npataTwo Currencies (JOI23_currencies)C++17
0 / 100
1201 ms1048576 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define vec vector const int N = 1<<17; const int CMX = (int)1<<31; struct Node { int cnt = 0; int sum = 0; Node* left = nullptr; Node* right = nullptr; Node* get_right() { if(right == nullptr) { right = new Node{}; } return right; } Node* get_left() { if(left == nullptr) { left = new Node{}; } return left; } void insert(int val, int l = 0, int r = CMX) { cnt++; sum += val; if(l+1 == r) return; int m = (l+r)/2; if(val >= m) { get_right()->insert(val, m, r); } else { get_left()->insert(val, l, m); } } ~Node() { delete left; delete right; } }; Node roots[N*3]; void insert(int i, int val) { i += N; roots[i].insert(val); while(i > 1) { i /= 2; roots[i].insert(val); } } int tree_sz[N]; int ri[N]; int t = 0; int depth[N]; vec<int> tree[N]; int par[N]; void dfs1(int u = 0, int p = -1) { par[u] = p; tree_sz[u] = 1; for(int v : tree[u]) { if(v == p) continue; depth[v] = depth[u]+1; dfs1(v, u); tree_sz[u] += tree_sz[v]; } } int head[N]; void heavy_light(int u = 0, int p = -1) { ri[u] = t++; pair<int, int> mxch{-1, -1}; for(int v : tree[u]) { if(v == p) continue; if(tree_sz[v] > mxch.second) { mxch = {v, tree_sz[v]}; } } if(mxch.first == -1) return; head[mxch.first] = head[u]; heavy_light(mxch.first, u); for(int v : tree[u]) { if(v == p || v == mxch.first) { continue; } head[v] = v; heavy_light(v, u); } } void tree_range_indices(int l, int r, vec<int>& res, int i = 1, int tl = 0, int tr = N) { if(tl >= r || tr <= l) return; if(tl >= l && tr <= r) { res.push_back(i); return; } int tm = (tl + tr)/2; tree_range_indices(l, r, res, i*2, tl, tm); tree_range_indices(l, r, res, i*2+1, tm, tr); } vec<int> range_indices(int u, int v) { vec<int> res = {}; while(true) { if(head[u] == head[v]) { if(depth[u] > depth[v]) swap(u, v); tree_range_indices(ri[u]+1, ri[v]+1, res); break; } if(depth[head[u]] < depth[head[v]]) swap(u, v); if(head[u] == u) { tree_range_indices(ri[u], ri[u]+1, res); u = par[u]; } else { tree_range_indices(ri[head[u]]+1, ri[u]+1, res); u = head[u]; } //cerr << "STUCK 2" << '\n'; } return res; } int32_t main() { int n, m, q; cin >> n >> m >> q; map<int, pair<int, int>> edges; for(int i = 0; i<n-1; i++) { int u, v; cin >> u >> v; u--;v--; tree[u].push_back(v); tree[v].push_back(u); edges.insert({i, {u, v}}); } dfs1(); heavy_light(); for(int i = 0; i<m; i++) { int ei, c; cin >> ei >> c; ei--; auto [u, v] = edges[ei]; if(depth[u] > depth[v]) swap(u, v); insert(ri[v], c); } for(int i = 0; i<q; i++) { int u, v, s, g; cin >> u >> v >> g >> s; u--; v--; vec<int> root_inds = range_indices(u, v); vec<Node*> nodes(root_inds.size()); int tot_cnt = 0; for(int i = 0; i<root_inds.size(); i++) { nodes[i] = &roots[root_inds[i]]; tot_cnt += nodes[i]->cnt; } int sum = 0; int cnt = 0; int l = 0; int r = CMX; while(l+1 != r) { int m = (l+r)/2; int cand_sum = sum; int cand_cnt = cnt; for(int i = 0; i<nodes.size(); i++) { cand_sum += nodes[i]->get_left()->sum; cand_cnt += nodes[i]->get_left()->cnt; } if(cand_sum <= s) { l = m; sum = cand_sum; cnt = cand_cnt; for(int i = 0; i<nodes.size(); i++) { nodes[i] = nodes[i]->get_right(); } } else { r = m; for(int i = 0; i<nodes.size(); i++) { nodes[i] = nodes[i]->get_left(); } } //cerr << "STUCK 1" << '\n'; } cerr << tot_cnt << ' ' << cnt << ' ' << g << '\n'; assert(sum <= s); if(g < tot_cnt-cnt) cout << -1 << endl; else cout << g-(tot_cnt-cnt) << endl; } }

Compilation message (stderr)

currencies.cpp: In function 'int32_t main()':
currencies.cpp:171:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |   for(int i = 0; i<root_inds.size(); i++) {
      |                  ~^~~~~~~~~~~~~~~~~
currencies.cpp:183:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |    for(int i = 0; i<nodes.size(); i++) {
      |                   ~^~~~~~~~~~~~~
currencies.cpp:191:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |     for(int i = 0; i<nodes.size(); i++) {
      |                    ~^~~~~~~~~~~~~
currencies.cpp:197:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |     for(int i = 0; i<nodes.size(); i++) {
      |                    ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...