Submission #860427

#	Time	Username	Problem	Language	Result	Execution time	Memory
860427		SuouYuki	Two Currencies (JOI23_currencies)	C++17	100 / 100	1117 ms	42512 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

int64_t f[100000], af[100000];

void update(int p, int x) {
      while (p < 100000) {
            f[p] += x;
            p |= p + 1;
      }
}

int64_t query(int p) {
      int64_t res = 0;
      while (p >= 0) {
            res += f[p];
            p = (p & (p + 1)) - 1;
      }
      return res;
}

void update(int p, int x, int y) {
      while (p < 100000) {
            f[p] += x;
            af[p] += y;
            p |= p + 1;
      }
}

pair<int64_t, int> duo_query(int p) {
      pair<int64_t, int> res{0, 0};
      while (p >= 0) {
            res.first += f[p];
            res.second += af[p];
            p = (p & (p + 1)) - 1;
      }
      return res;
}

int main() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);

      int n, m, q;
      cin >> n >> m >> q;

      vector<int> ce(n - 1);

      vector<vector<int>> adj(n);

      for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            u -= 1;
            v -= 1;
            adj[u].emplace_back(i);
            adj[v].emplace_back(i);
            ce[i] = u ^ v;
      }

      vector<int> cv;

      vector<pair<int, int>> cp(m);

      for (int i = 0; i < m; i++) {
            int u, x;
            cin >> u >> x;
            u -= 1;
            cp[i] = make_pair(u, x);
            cv.emplace_back(x);
      }

      sort(cv.begin(), cv.end());
      cv.erase(unique(cv.begin(), cv.end()), cv.end());

      vector<int> dfn(n), size(n), top(n), depth(n), parent(n), c(n - 1);
      {
            function<void(int)> dfs = [&](int u) -> void {
                  size[u] = 1;
                  for (int &i : adj[u]) {
                        int v = ce[i] ^ u;
                        adj[v].erase(find(adj[v].begin(), adj[v].end(), i));
                        c[i] = v;
                        dfs(v);
                        size[u] += size[v];
                        if (size[v] > size[ce[adj[u][0]] ^ u]) {
                              swap(adj[u][0], i);
                        }
                  }
            };
            dfs(0);

            int t = 0;
            dfs = [&](int u) -> void {
                  dfn[u] = t++;
                  for (int i : adj[u]) {
                        int v = ce[i] ^ u;
                        top[v] = (i == adj[u][0] ? top[u] : v);
                        depth[v] = depth[u] + 1;
                        parent[v] = u;
                        dfs(v);
                  }
            };
            dfs(0);

            parent[0] = -1;
      }

      int k = cv.size();
      vector<vector<int>> ev(k);

      for (auto [u, x] : cp) {
            u = c[u];
            x = lower_bound(cv.begin(), cv.end(), x) - cv.begin();
            ev[x].emplace_back(u);
            update(dfn[u], 1);
      }

      vector<int> s(q), t(q), x(q);
      vector<int64_t> y(q);
      for (int i = 0; i < q; i++) {
            cin >> s[i] >> t[i] >> x[i] >> y[i];
            s[i] -= 1;
            t[i] -= 1;
      }

      vector<int> cnt(q);
      for (int i = 0; i < q; i++) {
            int u = s[i];
            int v = t[i];
            while (top[u] != top[v]) {
                  if (depth[top[u]] > depth[top[v]]) {
                        swap(u, v);
                  }
                  cnt[i] += query(dfn[v]) - query(dfn[top[v]] - 1);
                  v = parent[top[v]];
            }
            if (depth[u] > depth[v]) {
                  swap(u, v);
            }
            cnt[i] += query(dfn[v]) - query(dfn[u]);
      }

      vector<int> mxa(q), last(q, -1);
      vector<int64_t> rem = y;

      vector<pair<int, int>> bs(q, make_pair(0, k));
      while (true) {
            bool fin = true;

            vector<vector<int>> qr(k);
            for (int i = 0; i < q; i++) {
                  if (bs[i].first < bs[i].second) {
                        int p = (bs[i].first + bs[i].second) / 2;
                        qr[p].emplace_back(i);
                        fin = false;
                  }
            }

            if (fin) {
                  break;
            }

            memset(f, 0, sizeof(f));
            memset(af, 0, sizeof(af));

            for (int i = 0; i < k; i++) {
                  for (int u : ev[i]) {
                        update(dfn[u], cv[i], 1);
                  }
                  for (int qi : qr[i]) {
                        int u = s[qi];
                        int v = t[qi];

                        int64_t sum = 0;
                        int num = 0;
                        while (top[u] != top[v]) {
                              if (depth[top[u]] > depth[top[v]]) {
                                    swap(u, v);
                              }
                              auto [sum1, num1] = duo_query(dfn[v]);
                              auto [sum2, num2] = duo_query(dfn[top[v]] - 1);
                              sum += sum1 - sum2;
                              num += num1 - num2;
                              v = parent[top[v]];
                        }
                        if (depth[u] > depth[v]) {
                              swap(u, v);
                        }
                        auto [sum1, num1] = duo_query(dfn[v]);
                        auto [sum2, num2] = duo_query(dfn[u]);
                        sum += sum1 - sum2;
                        num += num1 - num2;

                        if (sum <= y[qi]) {
                              mxa[qi] = num;
                              last[qi] = i;
                              rem[qi] = y[qi] - sum;
                              bs[qi].first = i + 1;
                        }
                        else {
                              bs[qi].second = i;
                        }
                  }
            }
      }

      for (int i = 0; i < q; i++) {
            if (last[i] + 1 < k) {
                  x[i] -= (cnt[i] - mxa[i] - rem[i] / cv[last[i] + 1]);
            }
            x[i] = max(x[i], -1);
            cout << x[i] << " \n"[i == n - 1];
      }

      return 0;
}

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