Submission #868420

#TimeUsernameProblemLanguageResultExecution timeMemory
868420t6twotwoTwo Currencies (JOI23_currencies)C++17
100 / 100
3431 ms167988 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class S, S (*f)(S, S), S e> struct PST { struct T { T *l, *r; S s; T() : s() {l = r = nullptr;} T(const S &v) : s(v) {l = r = nullptr;} T(T *t) : l(t->l), r(t->r), s(t->s) {} T(T *a, T *b) : l(a), r(b), s() { if (l) s = f(s, l->s); if (r) s = f(s, r->s); } }; int n; vector<T*> rts; PST(int m) : PST(vector<S>(m, e)) { } PST(const vector<S> &a) : n(a.size()) { function<T*(int, int)> bld = [&](int l, int r) { if (l + 1 == r) { return new T(a[l]); } int m = (l + r) / 2; return new T(bld(l, m), bld(m, r)); }; rts.push_back(bld(0, n)); } T* set(T *i, int l, int r, int p, const S &v) { if (l + 1 == r) { return new T(v); } int m = (l + r) / 2; if (p < m) { return new T(set(i->l, l, m, p, v), i->r); } else { return new T(i->l, set(i->r, m, r, p, v)); } } T* upd(T *i, int l, int r, int p, const S &v) { if (l + 1 == r) { return new T(f(i->s, v)); } int m = (l + r) / 2; if (p < m) { return new T(upd(i->l, l, m, p, v), i->r); } else { return new T(i->l, upd(i->r, m, r, p, v)); } } S qry(T *i, int l, int r, int L, int R) { if (R <= l || r <= L) { return e; } if (L <= l && r <= R) { return i->s; } int m = (l + r) / 2; return f(qry(i->l, l, m, L, R), qry(i->r, m, r, L, R)); } int lst() { return rts.size() - 1; } int cpy(int k) { rts.push_back(new T(rts[k])); return rts.size() - 1; } void set(int k, int i, const S &v) { rts[k] = set(rts[k], 0, n, i, v); } void upd(int k, int i, const S &v) { rts[k] = upd(rts[k], 0, n, i, v); } S qry(int k, int l, int r) { return qry(rts[k], 0, n, l, r); } }; ll F(ll x, ll y) { return x + y; } struct HLD { int n, timer; vector<int> sz, dep, par, top, pos; vector<vector<int>> adj; HLD(int n) : n(n) { sz.resize(n); dep.resize(n); top.resize(n); pos.resize(n); adj.resize(n); par.resize(n, -1); } void add_edge(int x, int y) { adj[x].push_back(y); adj[y].push_back(x); } void init(int x) { if (par[x] != -1) { adj[x].erase(find(adj[x].begin(), adj[x].end(), par[x])); } sz[x] = 1; for (int &y : adj[x]) { par[y] = x; dep[y] = dep[x] + 1; init(y); sz[x] += sz[y]; if (sz[y] > sz[adj[x][0]]) { swap(y, adj[x][0]); } } } void dfs(int x) { pos[x] = timer++; for (int y : adj[x]) { top[y] = y == adj[x][0] ? top[x] : y; dfs(y); } } void build() { init(0); timer = 0; dfs(0); } int lca(int x, int y) { for (; top[x] != top[y]; x = par[top[x]]) { if (dep[top[x]] < dep[top[y]]) { swap(x, y); } } return dep[x] < dep[y] ? x : y; } template <class T> void path(int x, int y, T f) { for (; top[x] != top[y]; x = par[top[x]]) { if (dep[top[x]] < dep[top[y]]) { swap(x, y); } f(pos[top[x]], pos[x] + 1); } if (dep[x] > dep[y]) { swap(x, y); } // f(pos[x], pos[y] + 1); f(pos[x] + 1, pos[y] + 1); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, Q; cin >> N >> M >> Q; vector<pair<int, int>> edges(N - 1); vector<vector<int>> adj(N); for (int i = 0; i < N - 1; i++) { int x, y; cin >> x >> y; x--, y--; edges[i] = {x, y}; adj[x].push_back(i); adj[y].push_back(i); } vector<pair<int, int>> ch(M); for (int i = 0; i < M; i++) { int p, c; cin >> p >> c; ch[i] = {c, p - 1}; } sort(ch.begin(), ch.end()); vector<int> t(N - 1); { auto dfs = [&](auto dfs, int x, int p) -> void { for (int z : adj[x]) { auto [u, v] = edges[z]; int y = x ^ u ^ v; if (y != p) { t[z] = y; dfs(dfs, y, x); } } }; dfs(dfs, 0, -1); } for (int i = 0; i < N; i++) { for (int &j : adj[i]) { auto [x, y] = edges[j]; j = i ^ x ^ y; } } HLD hld(N); for (int i = 0; i < N; i++) { for (int j : adj[i]) { if (i < j) { hld.add_edge(i, j); } } } hld.build(); PST<ll, F, 0> q(N); for (int i = 0; i < M; i++) { auto [c, p] = ch[i]; q.upd(q.cpy(q.lst()), hld.pos[t[p]], c); } auto get = [&](int x, int y, int z) { ll s = 0; hld.path(x, y, [&](int l, int r) { s += q.qry(z, l, r); }); return s; }; vector<int> S(Q), T(Q), X(Q), a(Q); vector<ll> Y(Q); for (int i = 0; i < Q; i++) { cin >> S[i] >> T[i] >> X[i] >> Y[i]; S[i]--, T[i]--; int lo = 0, hi = M; while (lo < hi) { int mi = (lo + hi + 1) / 2; if (get(S[i], T[i], mi) <= Y[i]) { lo = mi; } else { hi = mi - 1; } } a[i] = lo; } vector<ll> ans(Q); vector<vector<int>> f(M + 1); for (int i = 0; i < Q; i++) { f[a[i]].push_back(i); } q = PST<ll, F, 0>(N); assert(q.lst() == 0); for (int i = M; i >= 0; i--) { if (i < M) { auto [c, p] = ch[i]; q.upd(q.cpy(q.lst()), hld.pos[t[p]], 1); } for (int j : f[i]) { ans[j] = max(-1LL, X[j] - get(S[j], T[j], q.lst())); } } for (int i = 0; i < Q; i++) { cout << ans[i] << "\n"; } return 6/22; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...