Submission #825957

#TimeUsernameProblemLanguageResultExecution timeMemory
825957t6twotwoTwo Currencies (JOI23_currencies)C++17
10 / 100
5077 ms37448 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; 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; } } vector par(N, vector<int>(20, -1)); vector<int> dep(N), sz(N); auto init = [&](auto init, int x) -> void { for (int i = 0; i < 19 && par[x][i] != -1; i++) { par[x][i + 1] = par[par[x][i]][i]; } if (par[x][0] != -1) { adj[x].erase(find(adj[x].begin(), adj[x].end(), par[x][0])); } sz[x] = 1; for (int &y : adj[x]) { par[y][0] = x; dep[y] = dep[x] + 1; init(init, y); sz[x] += sz[y]; if (sz[y] > sz[adj[x][0]]) { swap(y, adj[x][0]); } } }; init(init, 0); vector<int> top(N), in(N); int timer = 0; auto dfs = [&](auto dfs, int x) -> void { in[x] = timer++; for (int y : adj[x]) { top[y] = adj[x][0] == y ? top[x] : y; dfs(dfs, y); } }; dfs(dfs, 0); auto lca = [&](int x, int y) { if (dep[x] < dep[y]) { swap(x, y); } for (int i = 0; i < 20; i++) { if ((dep[x] - dep[y]) >> i & 1) { x = par[x][i]; } } if (x == y) { return x; } for (int i = 19; i >= 0; i--) { if (par[x][i] != par[y][i]) { x = par[x][i]; y = par[y][i]; } } return par[x][0]; }; 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); 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; }; vector<ll> s(N); auto get = [&](int S, int T) { ll ans = 0; int P = lca(S, T); while (S != P) { ans += s[S]; S = par[S][0]; } while (T != P) { ans += s[T]; T = par[T][0]; } return ans; }; 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); } } s.assign(N, 0); for (int i = 0; i < M; i++) { auto [c, p] = ch[i]; s[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); } s.assign(N, 0); for (int i = M; i >= 0; i--) { if (i < M) { auto [c, p] = ch[i]; s[t[p]]++; } 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 function 'int main()':
currencies.cpp:108:10: warning: variable 'add' set but not used [-Wunused-but-set-variable]
  108 |     auto add = [&](int i, int v) {
      |          ^~~
currencies.cpp:113:10: warning: variable 'sum' set but not used [-Wunused-but-set-variable]
  113 |     auto sum = [&](int i) {
      |          ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...