Submission #868506

#TimeUsernameProblemLanguageResultExecution timeMemory
868506t6twotwoTwo Currencies (JOI23_currencies)C++17
100 / 100
1016 ms33344 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct HLD { bool e; int n, timer; vector<int> sz, dep, par, top, pos; vector<vector<int>> adj; HLD(int n, bool edge) : n(n), e(edge), sz(n), dep(n), top(n), pos(n), adj(n), par(n) { } void add_edge(int x, int y) { adj[x].push_back(y); adj[y].push_back(x); } void init(int x) { sz[x] = 1; for (int &y : adj[x]) { dep[y] = dep[x] + 1; adj[y].erase(find(adj[y].begin(), adj[y].end(), par[y] = x)); 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() { par[0] = -1; 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] + e, 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); } HLD hld(N, 1); for (int i = 0; i < N; i++) { for (int &j : adj[i]) { auto [x, y] = edges[j]; j = i ^ x ^ y; if (j < i) { hld.add_edge(i, j); } } } hld.build(); vector<int> S(Q), T(Q), X(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]--; if (S[i] > T[i]) { swap(S[i], T[i]); } } vector<int> lo(Q), hi(Q, M); vector<ll> bit(N + 1); auto add = [&](int i, int v) { for (i++; i <= N; i += i & -i) { bit[i] += v; } }; auto sum = [&](int i) { ll s = 0; for (; i; i -= i & -i) { s += bit[i]; } return s; }; auto get = [&](int x, int y) { ll s = 0; hld.path(x, y, [&](int l, int r) { s += sum(r) - sum(l); }); return s; }; for (int z = 0; z < 20; z++) { vector<int> mi(Q); vector<vector<int>> f(M); for (int i = 0; i < Q; i++) { if (lo[i] != hi[i]) { mi[i] = (lo[i] + hi[i] + 1) / 2; f[mi[i] - 1].push_back(i); } } bit.assign(N + 1, 0); for (int i = 0; i < M; i++) { auto [c, p] = ch[i]; add(hld.pos[t[p]], c); for (int j : f[i]) { if (get(S[j], T[j]) <= Y[j]) { lo[j] = i + 1; } else { hi[j] = i; } } } } vector<ll> ans(Q); vector<vector<int>> f(M + 1); for (int i = 0; i < Q; i++) { f[lo[i]].push_back(i); } bit.assign(N + 1, 0); for (int i = M; i >= 0; i--) { if (i < M) { auto [c, p] = ch[i]; add(hld.pos[t[p]], 1); } for (int j : f[i]) { ans[j] = max(-1LL, X[j] - get(S[j], T[j])); } } for (int i = 0; i < Q; i++) { cout << ans[i] << "\n"; } return 6/22; }

Compilation message (stderr)

currencies.cpp: In constructor 'HLD::HLD(int, bool)':
currencies.cpp:6:9: warning: 'HLD::n' will be initialized after [-Wreorder]
    6 |     int n, timer;
      |         ^
currencies.cpp:5:10: warning:   'bool HLD::e' [-Wreorder]
    5 |     bool e;
      |          ^
currencies.cpp:9:5: warning:   when initialized here [-Wreorder]
    9 |     HLD(int n, bool edge) : n(n), e(edge), sz(n),
      |     ^~~
currencies.cpp:8:25: warning: 'HLD::adj' will be initialized after [-Wreorder]
    8 |     vector<vector<int>> adj;
      |                         ^~~
currencies.cpp:7:26: warning:   'std::vector<int> HLD::par' [-Wreorder]
    7 |     vector<int> sz, dep, par, top, pos;
      |                          ^~~
currencies.cpp:9:5: warning:   when initialized here [-Wreorder]
    9 |     HLD(int n, bool edge) : n(n), e(edge), sz(n),
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...