제출 #769357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769357		peijar	Two Currencies (JOI23_currencies)	C++17	100 / 100	974 ms	50136 KiB

currencies

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template <class T> class Fenwick {
public:
  int lim;
  vector<T> bit;

  Fenwick(int n) : lim(n + 1), bit(lim) {}

  void upd(int pos, T val) {
    for (pos++; pos < lim; pos += pos & -pos)
      bit[pos] += val;
  }

  T sum(int r) { // < r
    T ret = 0;
    for (; r; r -= r & -r)
      ret += bit[r];
    return ret;
  }

  T sum(int l, int r) { // [l, r)
    return sum(r) - sum(l);
  }
};

const int MAXN = 1e5;
const int MAXP = 17;

int par[MAXP][MAXN];
vector<int> adj[MAXN];
int depth[MAXN], tin[MAXN], tout[MAXN];
int T;

void dfs(int u, int p) {
  tin[u] = T++;
  par[0][u] = p;
  for (int i = 0; i < MAXP - 1; ++i)
    par[i + 1][u] = par[i][par[i][u]];
  for (int v : adj[u])
    if (v != p) {
      depth[v] = depth[u] + 1;
      dfs(v, u);
    }
  tout[u] = T++;
}

int getLca(int u, int v) {
  if (depth[u] < depth[v])
    swap(u, v);
  int diff = depth[u] - depth[v];
  for (int p = 0; p < MAXP; ++p)
    if ((1 << p) & diff)
      u = par[p][u];
  if (u == v)
    return u;
  for (int p = MAXP - 1; p >= 0; --p)
    if (par[p][u] != par[p][v])
      u = par[p][u], v = par[p][v];

  return par[0][u];
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommets, nbPoids, nbRequetes;
  cin >> nbSommets >> nbPoids >> nbRequetes;

  vector<pair<int, int>> edges(nbSommets - 1);
  for (auto &[u, v] : edges) {
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  dfs(0, 0);
  vector<pair<int, int>> weights(nbPoids);
  for (int i = 0; i < nbPoids; ++i) {
    int p, c;
    cin >> p >> c;
    --p;
    auto [u, v] = edges[p];
    if (depth[u] > depth[v])
      swap(u, v);
    weights[i] = pair(c, v);
  }
  sort(weights.begin(), weights.end());

  vector<tuple<int, int, int, int>> queries(nbRequetes);
  for (auto &[s, t, gold, silver] : queries) {
    cin >> s >> t >> gold >> silver;
    --s, --t;
    if (tin[s] > tin[t])
      swap(s, t);
  }
  dbg(nbSommets, nbPoids, nbRequetes);
  vector<int> lca(nbRequetes);
  for (int i = 0; i < nbRequetes; ++i) {
    auto [s, t, gold, silver] = queries[i];
    lca[i] = getLca(s, t);
    dbg(s, t, lca[i]);
  }

  vector<int> lo(nbRequetes), up(nbRequetes, nbPoids);
  vector<int> cntFinal(nbRequetes, 1e18);
  vector<int> cntTotal(nbRequetes);

  while (true) {
    bool change = false;
    vector<vector<int>> needCheck(nbPoids + 1);
    for (int i = 0; i < nbRequetes; ++i) {
      if (lo[i] < up[i]) {
        int mid = (lo[i] + up[i] + 1) / 2;
        change = true;
        needCheck[mid].push_back(i);
      } else
        needCheck[lo[i]].push_back(i);
    }

    Fenwick<int> fenCnt(T), fenSum(T);

    for (int iPoids = 0; iPoids <= nbPoids; ++iPoids) {
      for (int iRequete : needCheck[iPoids]) {
        int l = lca[iRequete];
        auto [u, v, gold, silver] = queries[iRequete];
        int cnt = fenCnt.sum(tin[u] + 1) + fenCnt.sum(tin[v] + 1) -
                  2 * fenCnt.sum(tin[l] + 1);
        int sum = fenSum.sum(tin[u] + 1) + fenSum.sum(tin[v] + 1) -
                  2 * fenSum.sum(tin[l] + 1);
        cntFinal[iRequete] = cnt;
        if (sum <= silver)
          lo[iRequete] = iPoids;
        else
          up[iRequete] = iPoids - 1;
      }

      if (iPoids < nbPoids) {
        auto [c, u] = weights[iPoids];
        fenCnt.upd(tin[u], 1);
        fenCnt.upd(tout[u], -1);
        fenSum.upd(tin[u], c);
        fenSum.upd(tout[u], -c);
      }
    }
    for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
      int l = lca[iRequete];
      auto [u, v, gold, silver] = queries[iRequete];
      int cnt = fenCnt.sum(tin[u] + 1) + fenCnt.sum(tin[v] + 1) -
                2 * fenCnt.sum(tin[l] + 1);
      cntTotal[iRequete] = cnt;
    }
    if (!change)
      break;
  }
  for (int i = 0; i < nbRequetes; ++i) {
    auto [u, v, gold, silver] = queries[i];
    dbg(cntFinal[i], cntTotal[i]);
    cout << max(-1LL, gold - (cntTotal[i] - cntFinal[i])) << endl;
  }
}

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