Submission #965075

#	Time	Username	Problem	Language	Result	Execution time	Memory
965075		NeroZein	Two Currencies (JOI23_currencies)	C++17	0 / 100	11 ms	11068 KiB

currencies

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int LOG = 17;
const int N = 1e5 + 5; 

int n, m, q;
vector<int> g[N];
pair<int, int> edge[N];
pair<int, int> checkPoint[N];

int cnt;
int dep[N];
int up[LOG][N];
int in[N], out[N];

void dfs(int v, int p) {
  in[v] = ++cnt;
  for (int u : g[v]) {
    if (u == p) {
      continue; 
    }
    dep[u] = dep[v] + 1; 
    up[0][u] = v;
    for (int j = 1; j < LOG; ++j) {
      up[j][u] = up[j - 1][up[j - 1][u]]; 
    }
    dfs(u, v); 
  }
  out[v] = cnt; 
}

struct Query {
  int u, v, gold;
  long long silver;
  int l, r, m, ind, ans;
};

struct BIT {
  int n;
  vector<long long> tr;
  BIT(int n_) : n(n_) {
    tr.resize(n + 1); 
  }
  void upd(int p, int v) {
    while (p <= n) {
      tr[p] += v;
      p += p & -p;
    }
  }
  void upd(int l, int r, int v) {
    upd(l, v); upd(r + 1, -v); 
  }
  long long qry(int p) {
    long long ret = 0;
    while (p) {
      ret += tr[p];
      p -= p & -p;
    }
    return ret;
  }
};

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int j = 0; j < LOG; ++j) {
    if ((dep[u] - dep[v]) >> j & 1) {
      u = up[j][u];
    }
  }
  if (u == v) return v;
  for (int j = LOG - 1; j >= 0; --j) {
    if (up[j][u] != up[j][v]) {
      u = up[j][u]; v = up[j][v]; 
    }
  }
  return up[0][u];
}

Query qs[N];

void solve() {
  dfs(1, 1);
  for (int i = 1; i <= q; ++i) {
    qs[i].l = 0, qs[i].r = m, qs[i].ind = i; 
  }
  for (int i = 1; i < n; ++i) {
    if (dep[edge[i].first] > dep[edge[i].second]) {
      swap(edge[i].first, edge[i].second); 
    }
  }
  sort(checkPoint + 1, checkPoint + 1 + m, [&](pair<int, int>& i, pair<int, int>& j) {
    return i.second < j.second; 
  });
  for (int iter = 0; iter < 20; ++iter) {
    for (int i = 1; i <= q; ++i) {
      qs[i].m = (qs[i].l + qs[i].r + 1) / 2; 
    }
    sort(qs + 1, qs + 1 + q, [&](Query& i, Query& j) {
      return i.m < j.m;
    });
    BIT sum(n);
    int ptr = 1; 
    for (int i = 1; i <= q; ++i) {
      while (ptr <= qs[i].m) {
        int v = edge[checkPoint[ptr].first].second;
        sum.upd(in[v], out[v], checkPoint[ptr].second);
        ptr++;
      }
      long long t = sum.qry(in[qs[i].v]);
      t += sum.qry(in[qs[i].u]);
      t -= 2 * sum.qry(in[lca(qs[i].u, qs[i].v)]);
      if (t <= qs[i].silver) {
        qs[i].l = qs[i].m;
      } else {
        qs[i].r = qs[i].m - 1; 
      }
    }
  }
  sort(qs + 1, qs + 1 + q, [&](Query& i, Query& j) {
    return i.l < j.l;
  });
  BIT sum(n), ones(n);
  for (int i = 1; i <= m; ++i) {
    int v = edge[checkPoint[i].first].second; 
    ones.upd(in[v], out[v], 1);
  }
  int ptr = 1; 
  for (int i = 1; i <= q; ++i) {
    assert(qs[i].l == qs[i].r);
    while (ptr <= qs[i].l) {
      int v = edge[checkPoint[ptr].first].second; 
      ones.upd(in[v], out[v], -1);
      ptr++;
    }
    int t = ones.qry(in[qs[i].v]);
    t += ones.qry(in[qs[i].u]);
    t -= 2 * sum.qry(in[lca(qs[i].u, qs[i].v)]);
    qs[i].ans = qs[i].gold - t; 
  }
  sort(qs + 1, qs + 1 + q, [&](Query& i, Query& j) {
    return i.ind < j.ind;
  });
  for (int i = 1; i <= q; ++i) {
    cout << max(-1, qs[i].ans) << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m >> q;
  for(int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    edge[i] = {u, v};
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= m; ++i) {
    cin >> checkPoint[i].first >> checkPoint[i].second;//Edge index, Cj silver
  }
  for (int i = 1; i <= q; ++i) {
    cin >> qs[i].u >> qs[i].v >> qs[i].gold >> qs[i].silver;
    qs[i].ind = i; 
  }
  solve();
  return 0;
}

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