Submission #1050292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050292		QuangBui	Two Currencies (JOI23_currencies)	C++17	100 / 100	651 ms	49820 KiB

currencies

// QuangBuiCP
// https://oj.vnoi.info/problem/euler_k
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "local/debug.hpp"
#else
#define debug(...)
#endif // LOCAL

template <typename T>
struct Fenwick {
  int n;
  vector<T> tree;

  Fenwick(int n_) : n(n_) {
    tree.assign(n + 1, T());
  }

  void Add(int x, T val) {
    assert(1 <= x && x <= n);
    while (x <= n) {
      tree[x] += val;
      x += x & -x;
    }
  }

  T Get(int x) {
    T res = T();
    while (x >= 1) {
      res += tree[x];
      x -= x & -x;
    }
    return res;
  }
};

const int LOG = 18;

int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif // LOCAL

  int n, station, citizen;
  cin >> n >> station >> citizen;
  vector<int> u(n - 1), v(n - 1);
  for (int i = 0; i < n - 1; ++i) {
    cin >> u[i] >> v[i];
    u[i]--, v[i]--;
  }
  vector<int> pos(station), cost(station);
  for (int i = 0; i < station; ++i) {
    cin >> pos[i] >> cost[i];
    pos[i]--;
  }
  vector<int> start(citizen), end(citizen), gold(citizen);
  vector<int64_t> silver(citizen);
  for (int i = 0; i < citizen; ++i) {
    cin >> start[i] >> end[i] >> gold[i] >> silver[i];
    start[i]--, end[i]--;
  }

  vector<vector<int>> edge(n);
  for (int i = 0; i < n - 1; ++i) {
    edge[u[i]].push_back(v[i]);
    edge[v[i]].push_back(u[i]);
  }
  vector<int> par(n, -1), depth(n, 0);
  vector<vector<int>> childs(n);
  {
    queue<int> qu;
    qu.push(0);
    while (!qu.empty()) {
      int x = qu.front();
      qu.pop();
      for (int y : edge[x]) if (y != par[x]) {
        par[y] = x;
        childs[x].push_back(y);
        depth[y] = depth[x] + 1;
        qu.push(y);
      }
    }
  }

  for (int i = 0; i < n - 1; ++i) {
    if (v[i] == par[u[i]]) {
      swap(u[i], v[i]);
    }
  }

  vector<vector<int>> lift(LOG, vector<int>(n, -1));
  lift[0] = par;
  for (int i = 0; i < LOG - 1; ++i) {
    for (int j = 0; j < n; ++j) {
      if (lift[i][j] != -1) {
        lift[i + 1][j] = lift[i][lift[i][j]];
      }
    }
  }

  vector<int> lca(citizen); // LCA(start[i], end[i])
  for (int i = 0; i < citizen; ++i) {
    int x = start[i], y = end[i];
    if (depth[x] < depth[y]) {
      swap(x, y);
    }
    for (int j = 0; j < LOG; ++j) {
      if ((depth[x] - depth[y]) >> j & 1) {
        x = lift[j][x];
      }
    }
    if (x == y) {
      lca[i] = x;
      continue;
    }
    for (int j = LOG - 1; j >= 0; --j) {
      if (lift[j][x] != lift[j][y]) {
        x = lift[j][x];
        y = lift[j][y];
      }
    }
    lca[i] = par[x];
  }

  vector<int> tin(n), tout(n);
  {
    int timer = 0;
    auto Dfs = [&](auto&& self, int x) -> void {
      if (x != 0) {
        tin[x] = ++timer;
      }
      for (int y : childs[x]) {
        self(self, y);
      }
      if (x != 0) {
        tout[x] = ++timer;
      }
    };
    Dfs(Dfs, 0);
    tin[0] = -1;
  }

  vector<int> order(station);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&pos, &cost](int i, int j) {
    if (cost[i] == cost[j]) {
      return pos[i] < pos[j];
    }
    return cost[i] < cost[j];
  });

  vector<int> L(citizen, 0), R(citizen, station);
  vector<int> used(citizen);
  vector<vector<int>> candidates(station + 1);
  for (int step = 0; step < 18; ++step) {
    for (int i = 0; i < citizen; ++i) {
      if (L[i] > R[i]) {
        continue;
      }
      candidates[(L[i] + R[i]) / 2].push_back(i);
    }
    Fenwick<int> f(n * 2);
    Fenwick<int64_t> g(n * 2);
    for (int i = 0; i < station; ++i) {
      f.Add(tin[v[pos[i]]], 1);
      f.Add(tout[v[pos[i]]], -1);
    }
    for (int mid = 0; mid <= station; ++mid) {
      for (int who : candidates[mid]) {
        int64_t sum = g.Get(tin[start[who]]) + g.Get(tin[end[who]])
                     - g.Get(tin[lca[who]]) * 2;
        if (sum <= silver[who]) {
          used[who] = f.Get(tin[start[who]]) + f.Get(tin[end[who]])
                     - f.Get(tin[lca[who]]) * 2;
          L[who] = mid + 1;
        } else {
          R[who] = mid - 1;
        }
      }
      if (mid < station) {
        int node = pos[order[mid]];
        int val = cost[order[mid]];
        f.Add(tin[v[node]], -1);
        f.Add(tout[v[node]], 1);
        g.Add(tin[v[node]], val);
        g.Add(tout[v[node]], -val);
      }
      candidates[mid].clear();
    }
  }

  debug(lca);
  for (int i = 0; i < citizen; ++i) {
    cout << max(gold[i] - used[i], -1) << '\n';
  }

  return 0;
}

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