Submission #794174

#	Time	Username	Problem	Language	Result	Execution time	Memory
794174		ind1v	Two Currencies (JOI23_currencies)	C++11	100 / 100	1491 ms	41352 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

struct fenwick_tree {
  long long fenw[N];
  
  fenwick_tree() {
    memset(fenw, 0, sizeof(fenw));
  }
  
  void reset() {
    memset(fenw, 0, sizeof(fenw));
  }
  
  void upd(int idx, int val) {
    for (; idx < N; idx |= (idx + 1)) {
      fenw[idx] += val;
    }
  }
  
  long long get(int idx) {
    long long res = 0;
    for (; idx >= 0; idx &= (idx + 1), --idx) {
      res += fenw[idx];
    }
    return res;
  }
  
  long long get(int l, int r) {
    return get(r) - get(l - 1);
  }
};

int n, m, q;
int a[N], b[N];
int p[N], c[N];
int ord[N];
int s[N], t[N], x[N];
long long y[N];
int l[N], r[N], ans[N];
vector<int> cand[N];
vector<pair<int, int>> g[N];
int dep[N], sz[N], son[N], fa[N], head[N], pos[N];
int hld_timer = 0;
fenwick_tree gold, silver;

void dfs(int u, int p, int d, int pid) {
  sz[u] = 1;
  fa[u] = p;
  dep[u] = d;
  int mx = 0;
  for (pair<int, int> &e : g[u]) {
    int v, id;
    tie(v, id) = e;
    if (id == pid) {
      continue;
    }
    dfs(v, u, d + 1, id);
    sz[u] += sz[v];
    if (sz[v] > mx) {
      mx = sz[v];
      son[u] = v;
    }
  }
}

void decompose(int u, int p, int h) {
  head[u] = h;
  pos[u] = ++hld_timer;
  if (son[u] != 0) {
    decompose(son[u], u, h);
  }
  for (pair<int, int> &e : g[u]) {
    int v, id;
    tie(v, id) = e;
    if (v == p || v == son[u]) {
      continue;
    }
    decompose(v, u, v);
  }
}

void silver_upd(int i, int w) {
  int u = dep[a[i]] > dep[b[i]] ? a[i] : b[i];
  silver.upd(pos[u], w);
}

void gold_upd(int i, int w) {
  int u = dep[a[i]] > dep[b[i]] ? a[i] : b[i];
  gold.upd(pos[u], w);
}

int gold_que(int u, int v) {
  int sum = 0;
  while (head[u] != head[v]) {
    if (dep[head[u]] > dep[head[v]]) {
      swap(u, v);
    }
    sum += gold.get(pos[head[v]], pos[v]);
    v = fa[head[v]];
  }
  if (dep[u] > dep[v]) {
    swap(u, v);
  }
  if (pos[u] < pos[v]) {
    sum += gold.get(pos[u] + 1, pos[v]);
  }
  return sum;
}

long long silver_que(int u, int v) {
  long long sum = 0;
  while (head[u] != head[v]) {
    if (dep[head[u]] > dep[head[v]]) {
      swap(u, v);
    }
    sum += silver.get(pos[head[v]], pos[v]);
    v = fa[head[v]];
  }
  if (dep[u] > dep[v]) {
    swap(u, v);
  }
  if (pos[u] < pos[v]) {
    sum += silver.get(pos[u] + 1, pos[v]);
  }
  return sum;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i <= n - 1; i++) {
    cin >> a[i] >> b[i];
    g[a[i]].emplace_back(b[i], i);
    g[b[i]].emplace_back(a[i], i);
  }
  dfs(1, 1, 0, 0);
  decompose(1, 1, 1);
  for (int i = 1; i <= m; i++) {
    cin >> p[i] >> c[i];
  }
  iota(ord + 1, ord + m + 1, 1);
  sort(ord + 1, ord + m + 1, [](const int &u, const int &v) -> bool {
    return c[u] < c[v];
  });
  for (int i = 1; i <= q; i++) {
    cin >> s[i] >> t[i] >> x[i] >> y[i];
    l[i] = 1;
    r[i] = m + 1;
    ans[i] = -1;
  }
  for (int ite = 1; ite <= 20; ite++) {
    silver.reset();
    gold.reset();
    for (int i = 1; i <= m; i++) {
      silver_upd(p[i], c[i]);
    }
    for (int i = 1; i <= m + 1; i++) {
      cand[i].clear();
    }
    for (int i = 1; i <= q; i++) {
      if (l[i] > r[i]) {
        continue;
      }
      cand[l[i] + r[i] >> 1].emplace_back(i);
    }
    for (int i = m + 1; i >= 1; i--) {
      if (i != m + 1) {
        silver_upd(p[ord[i]], -c[ord[i]]);
        gold_upd(p[ord[i]], +1);
      }
      for (int &idx : cand[i]) {
        if (silver_que(s[idx], t[idx]) <= y[idx]) {
          if (gold_que(s[idx], t[idx]) <= x[idx]) {
            ans[idx] = x[idx] - gold_que(s[idx], t[idx]);
          }
          l[idx] = i + 1;
        } else {
          r[idx] = i - 1;
        }
      }
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:169:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |       cand[l[i] + r[i] >> 1].emplace_back(i);
      |            ~~~~~^~~~~~

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