Submission #976291

#	Time	Username	Problem	Language	Result	Execution time	Memory
976291		mannshah1211	Two Currencies (JOI23_currencies)	C++17	100 / 100	1067 ms	157360 KiB

currencies

/**
 *  author: hashman
 *  created:
**/

#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

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

void debug_out() {
  cerr << endl;
}

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

using Int = long long;

#define int Int

struct node {
  node *l, *r;
  int len;
  Int sum;
  
  node(int y, Int x) : l(nullptr), r(nullptr), len(y), sum(x) {}
  
  node(node *ll, node *rr) : l(ll), r(rr), len(0), sum(Int(0)) {
    if (ll) {
      len += ll->len;
      sum += ll->sum;
    }
    if (rr) {
      len += rr->len;
      sum += rr->sum;
    }
  }
  
  node(node *copy) : l(copy->l), r(copy->r), sum(copy->sum) {}
};

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  vector<vector<int>> g(n);
  vector<pair<int, int>> ed(n - 1);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    g[a].push_back(b);
    g[b].push_back(a);
    ed[i] = make_pair(a, b);
  }
  vector<int> d(n);
  vector<vector<int>> up(n, vector<int>(18));
  auto dfs = [&](auto&& self, int v, int pr) -> void {
    up[v][0] = pr;
    for (int u : g[v]) {
      if (u != pr) {
        d[u] = d[v] + 1;
        self(self, u, v);
      }
    }
  };
  dfs(dfs, 0, -1);
  for (int j = 1; j < 18; j++) {
    for (int i = 0; i < n; i++) {
      up[i][j] = (up[i][j - 1] == -1 ? -1 : up[up[i][j - 1]][j - 1]);
    }
  }
  auto kth = [&](int v, int k) {
    for (int b = 17; b >= 0; b--) {
      if (k & (1 << b)) {
        v = up[v][b];
        if (v == -1) {
          return v;
        }
      }
    }
    return v;
  };
  auto lca = [&](int u, int v) {
    if (d[u] < d[v]) {
      swap(u, v);
    }
    u = kth(u, d[u] - d[v]);
    for (int b = 17; b >= 0; b--) {
      if (up[u][b] != up[v][b] && up[u][b] != -1 && up[v][b] != -1) {
        u = up[u][b];
        v = up[v][b];
      }
    }
    return (u == v) ? v : up[v][0];
  };
  vector<vector<int>> at(n);
  vector<int> cp(m);
  vector<int> till(n);
  for (int i = 0; i < m; i++) {
    int p, c;
    cin >> p >> c;
    --p;
    if (d[ed[p].first] > d[ed[p].second]) {
      swap(ed[p].first, ed[p].second);
    }
    at[ed[p].second].push_back(c);
    cp[i] = c;
  }
  sort(cp.begin(), cp.end());
  map<int, int> compress, inv;
  int cnt = 0;
  for (int i = 0; i < m; i++) {
    compress[cp[i]] = -1;
  }
  for (int i = 0; i < m; i++) {
    if (compress[cp[i]] == -1) {
      compress[cp[i]] = cnt++;
      inv[compress[cp[i]]] = cp[i];
    }
  }
  vector<node*> roots(max(n, m));
  auto build = [&](auto&& self, int l, int r) {
    if (r - l == 1) {
      return new node(0, Int(0));
    }
    int m = (l + r) / 2;
    return new node(self(self, l, m), self(self, m, r));
  };
  auto modify = [&](auto&& self, node *nd, int orig, int i, int l, int r) {
    if (r - l == 1) {
      return new node(nd->len + 1, nd->sum + orig);
    }
    int m = (l + r) / 2;
    if (i < m) {
      return new node(self(self, nd->l, orig, i, l, m), nd->r);
    } else {
      return new node(nd->l, self(self, nd->r, orig, i, m, r));
    }
  };
  auto apply = [&](auto&& self, int v, int pr) -> void {
    if (pr != -1) {
      roots[v] = roots[pr];
      for (int change : at[v]) {
        roots[v] = modify(modify, roots[v], change, compress[change], 0, max(n, m));
      }
    }
    for (int u : g[v]) {
      if (u != pr) {
        till[u] = till[v] + (int) at[u].size();
        self(self, u, v);
      }
    }
  };
  roots[0] = build(build, 0, max(n, m));
  apply(apply, 0, -1);
  auto find = [&](auto&& self, node *a, node *b, node *c, Int k, int l, int r) {
    if (r - l == 1) {
      if (inv[l] == 0) {
        return Int(0);
      }
      return min(a->len + b->len - (2 * c->len), k / inv[l]);
    }
    int m = (l + r) / 2;
    Int lft = (a->l->sum) + (b->l->sum) - (2 * (c->l->sum));
    if (lft >= k) {
      return self(self, a->l, b->l, c->l, k, l, m);
    } else {
      return a->l->len + b->l->len - (2 * (c->l->len)) + self(self, a->r, b->r, c->r, k - lft, m, r);
    }
  };
  auto num = [&](int u, int v) {
    return till[u] + till[v] - (2 * till[lca(u, v)]);
  };
  for (int i = 0; i < q; i++) {
    int s, t, x;
    cin >> s >> t >> x;
    --s; --t;
    Int y;
    cin >> y;
    int anc = lca(s, t), res = find(find, roots[s], roots[t], roots[anc], y, 0, max(n, m));
    if (num(s, t) - res > x) {
      cout << -1 << '\n';
    } else {
      cout << x + res - num(s, t) << '\n';
    }
  }
}

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