Submission #952472

#	Time	Username	Problem	Language	Result	Execution time	Memory
952472		abczz	Two Currencies (JOI23_currencies)	C++14	100 / 100	2257 ms	111812 KiB

currencies

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <array>
#include <map>
#define ll long long

using namespace std;

ll n, m, q, a, b, x, y, c, s, cnt, tot, l, r, mid, f, sz[100000], P[100000], D[100000], bl[100000][18];
vector <ll> G[100000];
vector <ll> E[100000];
vector <array<ll, 2> > Q;
array <ll, 2> X[100000];
map <ll, ll> mp;
vector <ll> V;
vector <array<ll, 2> > adj[100000];

void dfs(ll u, ll p) {
  ++sz[u];
  for (auto [v, x] : adj[u]) {
    if (v != p) {
      D[v] = D[u] + 1;
      bl[v][0] = u;
      dfs(v, u);
      P[v] = x;
      sz[u] += sz[v];
    }
  }
}

void hld(ll u, ll p, ll g) {
  ll mxsz = -1, id = -1;
  X[u] = {g, (ll)G[g].size()};
  G[g].push_back(u);
  for (auto [v, x] : adj[u]) {
    if (v != p) {
      if (sz[v] > mxsz) {
        mxsz = sz[v];
        id = v;
      }
    }
  }
  if (id != -1) hld(id, u, g);
  for (auto [v, x] : adj[u]) {
    if (v != p && v != id) {
      hld(v, u, ++cnt);
    }
  }
}

struct SegTree{
  ll grp;
  vector <vector<ll> > st;
  vector <vector<ll> > ps;
  void init() {
    st.resize(G[grp].size() * 4);
    ps.resize(G[grp].size() * 4);
    build(1, 0, G[grp].size()-1);
  }
  void build(ll id, ll l, ll r) {
    if (l == r) {
      swap(st[id], E[P[G[grp][l]]]);
      for (int i=0; i<st[id].size(); ++i) {
        ps[id].push_back(st[id][i] + (ps[id].empty() ? 0 : ps[id].back()));
      }
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    int i = 0, j = 0;
    while (i < st[id*2].size() && j < st[id*2+1].size()) {
      if (st[id*2][i] < st[id*2+1][j]) st[id].push_back(st[id*2][i++]);
      else st[id].push_back(st[id*2+1][j++]);
      ps[id].push_back(st[id][i+j-1] + (ps[id].empty() ? 0 : ps[id].back()));
    }
    while (i < st[id*2].size()) {
      st[id].push_back(st[id*2][i++]);
      ps[id].push_back(st[id][i+j-1] + (ps[id].empty() ? 0 : ps[id].back()));
    }
    while (j < st[id*2+1].size()) {
      st[id].push_back(st[id*2+1][j++]);
      ps[id].push_back(st[id][i+j-1] + (ps[id].empty() ? 0 : ps[id].back()));
    }
  }
  void query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
      Q.push_back({grp, id});
      return;
    }
    ll mid = (l+r)/2;
    query(id*2, l, mid, ql, qr);
    query(id*2+1, mid+1, r, ql, qr);
  }
};
vector <SegTree> sg;

ll lca(ll a, ll b) {
  if (D[a] > D[b]) swap(a, b);
  ll db = D[b];
  for (int i=17; i>=0; --i) {
    if (db-(1LL<<i) >= D[a]) {
      db -= (1LL<<i);
      b = bl[b][i];
    }
  }
  for (int i=17; i>=0; --i) {
    if (bl[a][i] != bl[b][i]) {
      a = bl[a][i];
      b = bl[b][i];
    }
  }
  if (a != b) return D[a]-1;
  else return D[a];
}

void solve(ll u, ll d) {
  auto [x, y] = X[u];
  if (d < D[G[x][0]]) {
    sg[x].query(1, 0, G[x].size()-1, 0, y);
    if (d+1 < D[G[x][0]]) solve(bl[G[x][0]][0], d);
  }
  else sg[x].query(1, 0, G[x].size()-1, d-D[G[x][0]]+1, y);
}

int main() {
  cin >> n >> m >> q;
  P[0] = n-1;
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[a].push_back({b, i});
    adj[b].push_back({a, i});
  }
  dfs(0, -1);
  hld(0, -1, 0);
  for (int j=1; j<18; ++j) {
    for (int i=0; i<n; ++i) {
      bl[i][j] = bl[bl[i][j-1]][j-1];
    }
  }
  for (int i=0; i<m; ++i) {
    cin >> a >> b;
    --a;
    ++mp[b];
    E[a].push_back(b);
  }
  for (auto [x, y] : mp) {
    V.push_back(x);
  }
  for (int i=0; i<n-1; ++i) {
    sort(E[i].begin(), E[i].end());
  }
  for (int i=0; i<=cnt; ++i) {
    SegTree cur;
    sg.push_back(cur);
    sg[i].grp = i;
    sg[i].init();
  }
  while (q--) {
    Q.clear();
    cin >> a >> b >> x >> y;
    --a, --b;
    c = lca(a, b);
    solve(a, c);
    solve(b, c);
    l = 0, r = V.size()-1;
    tot = 0;
    for (auto [g, id] : Q) {
      tot += sg[g].st[id].size();
    }
    while (l < r) {
      mid = (l+r+1)/2;
      s = 0;
      for (auto [g, id] : Q) {
        auto it = lower_bound(sg[g].st[id].begin(), sg[g].st[id].end(), V[mid]+1);
        if (it != sg[g].st[id].begin()) {
          it = prev(it);
          s += sg[g].ps[id][it-sg[g].st[id].begin()];
        }
      }
      if (s <= y) l = mid;
      else r = mid-1;
    }
    f = s = 0;
    for (auto [g, id] : Q) {
      auto it = lower_bound(sg[g].st[id].begin(), sg[g].st[id].end(), V[l]+1);
      if (it != sg[g].st[id].begin()) {
        it = prev(it);
        f += it-sg[g].st[id].begin() + 1;
        s += sg[g].ps[id][it-sg[g].st[id].begin()];
      }
    }
    if (s > y) s = f = 0, l = -1;
    if (s <= y && l != V.size()-1) f += (y-s) / V[l+1];
    cout << max((ll)-1, x-(tot-f)) << '\n';
  }
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(long long int, long long int)':
currencies.cpp:22:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |   for (auto [v, x] : adj[u]) {
      |             ^
currencies.cpp: In function 'void hld(long long int, long long int, long long int)':
currencies.cpp:37:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |   for (auto [v, x] : adj[u]) {
      |             ^
currencies.cpp:46:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |   for (auto [v, x] : adj[u]) {
      |             ^
currencies.cpp: In member function 'void SegTree::build(long long int, long long int, long long int)':
currencies.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |       for (int i=0; i<st[id].size(); ++i) {
      |                     ~^~~~~~~~~~~~~~
currencies.cpp:74:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~
currencies.cpp:74:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |                                   ~~^~~~~~~~~~~~~~~~~~~
currencies.cpp:79:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     while (i < st[id*2].size()) {
      |            ~~^~~~~~~~~~~~~~~~~
currencies.cpp:83:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     while (j < st[id*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'void solve(long long int, long long int)':
currencies.cpp:121:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |   auto [x, y] = X[u];
      |        ^
currencies.cpp: In function 'int main()':
currencies.cpp:151:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |   for (auto [x, y] : mp) {
      |             ^
currencies.cpp:172:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  172 |     for (auto [g, id] : Q) {
      |               ^
currencies.cpp:178:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  178 |       for (auto [g, id] : Q) {
      |                 ^
currencies.cpp:189:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  189 |     for (auto [g, id] : Q) {
      |               ^
currencies.cpp:198:21: 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]
  198 |     if (s <= y && l != V.size()-1) f += (y-s) / V[l+1];
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32