Submission #729015

#	Time	Username	Problem	Language	Result	Execution time	Memory
729015		MilosMilutinovic	Two Currencies (JOI23_currencies)	C++14	100 / 100	4624 ms	93864 KiB

currencies

/**
 *    author:  wxhtzdy
 *    created: 19.03.2023 07:01:27
**/
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
const int L = 18;
const int M = N * 32;
const int inf = (int) 1e9 + 1;

int rt[N], cs[N], tsz, ls[M], rs[M], cnt[M];
long long sum[M];
vector<int> g[N];
int pr[N][L];
int x[N], y[N], dep[N];

void Modify(int& v, int p, int l, int r, int x, int d) {
  v = ++tsz;
  ls[v] = ls[p];
  rs[v] = rs[p];
  cnt[v] = cnt[p] + d;
  sum[v] = sum[p] + x * d;
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  if (x <= mid) {
    Modify(ls[v], ls[p], l, mid, x, d);
  } else {
    Modify(rs[v], rs[p], mid + 1, r, x, d);
  }
}

int GetCnt(int v, int l, int r, int ql, int qr) {
  if (!v || l > r || ql > qr || l > qr || r < ql) {
    return 0;
  }
  if (ql <= l && r <= qr) {
    return cnt[v];
  }
  int mid = l + r >> 1;
  return GetCnt(ls[v], l, mid, ql, qr) + GetCnt(rs[v], mid + 1, r, ql, qr);
}

long long GetSum(int v, int l, int r, int ql, int qr) {
  if (!v || l > r || ql > qr || l > qr || r < ql) {
    return 0LL;
  }
  if (ql <= l && r <= qr) {
    return sum[v];
  }
  int mid = l + r >> 1;
  return GetSum(ls[v], l, mid, ql, qr) + GetSum(rs[v], mid + 1, r, ql, qr);
}

int FindFirst(int v0, int v1, int v2, int l, int r, int x) {
  if (l == r) {
    return l;
  }
  int mid = l + r >> 1;
  int L = cnt[ls[v0]] + cnt[ls[v1]] - 2 * cnt[ls[v2]];
  if (L >= x) {
    return FindFirst(ls[v0], ls[v1], ls[v2], l, mid, x);
  } else {
    return FindFirst(rs[v0], rs[v1], rs[v2], mid + 1, r, x - L);
  }
}

void Go(int v, int pv) {
  for (int u : g[v]) {
    if (u == pv) {
      continue;
    }
    dep[u] = dep[v] + 1;
    Go(u, v);
  }
}

vector<int> qs[N];

void Dfs(int v, int pv) {
  pr[v][0] = pv;
  for (int j = 1; j < L; j++) {
    pr[v][j] = pr[pr[v][j - 1]][j - 1];  
  }
  for (int c : qs[v]) {
    Modify(rt[v], rt[v], 1, inf, c, +1);
    cs[v] += 1;  
  }
  for (int u : g[v]) {
    if (u == pv) {
      continue;
    }
    rt[u] = rt[v];
    cs[u] = cs[v];
    Dfs(u, v);
  }
}

int LCA(int x, int y) {
  if (dep[x] > dep[y]) {
    swap(x, y);
  }
  for (int j = L - 1; j >= 0; j--) {
    if (dep[pr[y][j]] >= dep[x]) {
      y = pr[y][j];
    }
  }
  for (int j = L - 1; j >= 0; j--) {
    if (pr[x][j] != pr[y][j]) {
      x = pr[x][j];
      y = pr[y][j];
    }
  }
  return (x == y ? x : pr[x][0]);
}
  
long long  Get(int s, int t, int w, int f) {
  int p = FindFirst(rt[s], rt[t], rt[w], 1, inf, f);
  int cc = GetCnt(rt[s], 1, inf, 1, p - 1) + GetCnt(rt[t], 1, inf, 1, p - 1)
         - 2 * GetCnt(rt[w], 1, inf, 1, p - 1);
  long long res = GetSum(rt[s], 1, inf, 1, p - 1) + GetSum(rt[t], 1, inf, 1, p - 1)
                - 2 * GetSum(rt[w], 1, inf, 1, p - 1);
  res += p * 1LL * (f - cc);
  return res;      
}
      

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m, q;
  cin >> n >> m >> q;
  for (int i = 1; i < n; i++) {
    cin >> x[i] >> y[i];
    --x[i]; --y[i];
    g[x[i]].push_back(y[i]);
    g[y[i]].push_back(x[i]);
  }
  Go(0, 0);
  for (int i = 1; i < n; i++) {
    if (dep[x[i]] > dep[y[i]]) {
      swap(x[i], y[i]);
    }
  }
  for (int i = 0; i < m; i++) {
    int p, c;
    cin >> p >> c;
    qs[y[p]].push_back(c);
  }
  Dfs(0, 0);
  while (q--) {
    int s, t, a;
    long long b;
    cin >> s >> t >> a >> b;
    --s; --t;
    int w = LCA(s, t);
    int f = cs[s] + cs[t] - 2 * cs[w];
    int low = 0, high = a, ans = -1;
    while (low <= high) {
      int mid = low + high >> 1;
      if (Get(s, t, w, max(0, f - (a - mid))) <= b) {
        ans = mid;
        low = mid + 1;  
      } else {
        high = mid - 1;
      }
    }  
    cout << ans << '\n';
  }                                        
  return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void Modify(int&, int, int, int, int, int)':
currencies.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid = l + r >> 1;
      |             ~~^~~
currencies.cpp: In function 'int GetCnt(int, int, int, int, int)':
currencies.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int mid = l + r >> 1;
      |             ~~^~~
currencies.cpp: In function 'long long int GetSum(int, int, int, int, int)':
currencies.cpp:55:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int mid = l + r >> 1;
      |             ~~^~~
currencies.cpp: In function 'int FindFirst(int, int, int, int, int, int)':
currencies.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   int mid = l + r >> 1;
      |             ~~^~~
currencies.cpp: In function 'int main()':
currencies.cpp:164:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  164 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~

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