Submission #1217606

#TimeUsernameProblemLanguageResultExecution timeMemory
1217606BuiDucManh123Two Currencies (JOI23_currencies)C++20
100 / 100
393 ms33084 KiB
#include <bits/stdc++.h> #define fi first #define se second #define ll long long #define ull unsigned long long #define pii pair<int, int> #define pll pair<ll, ll> #define pb push_back #define taskname "" const int mod=1e9+7; using namespace std; const int MAXN = 200005; const int LOGN = 20; struct Edge { int u, v; }; int n, m, q; Edge ee[MAXN]; vector<int> g[MAXN]; int tin[MAXN], tout[MAXN], timerDFS; int up[LOGN][MAXN]; int depthArr[MAXN]; struct Fenwick { int n; vector<ll> bit; Fenwick() {} Fenwick(int _n) { init(_n); } void init(int _n) { n = _n; bit.assign(n + 2, 0); } void update(int i, ll v) { for (; i <= n; i += i & -i) bit[i] += v; } void range_add(int l, int r, ll v) { if (l > r) return; update(l, v); if (r + 1 <= n) update(r + 1, -v); } ll point_get(int i) const { ll s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; } } fenw; void dfs(int u, int p) { tin[u] = ++timerDFS; up[0][u] = (p == -1 ? u : p); depthArr[u] = (p == -1 ? 0 : depthArr[p] + 1); for (int v : g[u]) { if (v == p) continue; dfs(v, u); } tout[u] = timerDFS; } int lca(int u, int v) { if (depthArr[u] < depthArr[v]) swap(u, v); int diff = depthArr[u] - depthArr[v]; for (int k = 0; k < LOGN; k++) { if (diff & (1 << k)) { u = up[k][u]; } } if (u == v) return u; for (int k = LOGN - 1; k >= 0; k--) { if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; } } return up[0][u]; } struct Item { int v; ll c; } items[MAXN]; vector<int> orig_s, orig_t, orig_x_int, orig_y_int; vector<ll> orig_x, orig_y; vector<int> ansIndex; struct RecQ { int id, s, t, lca; ll y; }; ll path_sum_cost(const RecQ* qr) { int s = qr->s, t = qr->t, lc = qr->lca; return fenw.point_get(tin[s]) + fenw.point_get(tin[t]) - 2 * fenw.point_get(tin[lc]); } void solve_rec(int l, int r, vector<RecQ*>& vec) { if (vec.empty()) return; if (l > r) { for (RecQ* p : vec) { ansIndex[p->id] = 0; } return; } if (l == r) { for (RecQ* p : vec) { ansIndex[p->id] = l; } return; } int mid = (l + r) / 2 + 1; for (int i = l + 1; i <= mid; i++) { int u = items[i].v; fenw.range_add(tin[u], tout[u], items[i].c); } vector<RecQ*> left, right; left.reserve(vec.size()); right.reserve(vec.size()); for (RecQ* p : vec) { ll sumc = path_sum_cost(p); if (p->y < sumc) { left.pb(p); } else { right.pb(p); } } if (!right.empty()) { solve_rec(mid, r, right); } for (int i = l + 1; i <= mid; i++) { int u = items[i].v; fenw.range_add(tin[u], tout[u], -items[i].c); } if (!left.empty()) { solve_rec(l, mid - 1, left); } } int main() { if (fopen(taskname".inp","r")) { freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> q; for (int i = 1; i <= n - 1; i++) { cin >> ee[i].u >> ee[i].v; g[ee[i].u].pb(ee[i].v); g[ee[i].v].pb(ee[i].u); } timerDFS = 0; dfs(1, -1); for (int k = 1; k < LOGN; k++) { for (int u = 1; u <= n; u++) { up[k][u] = up[k - 1][ up[k - 1][u] ]; } } for (int i = 1; i <= m; i++) { int eid; ll c; cin >> eid >> c; int u = ee[eid].u, v = ee[eid].v; if (depthArr[u] < depthArr[v]) swap(u, v); items[i].v = u; items[i].c = c; } sort(items + 1, items + m + 1, [&](const Item &a, const Item &b) { return a.c < b.c; }); orig_s.resize(q); orig_t.resize(q); orig_x.resize(q); orig_y.resize(q); vector<RecQ> recq(q); for (int i = 0; i < q; i++) { int s, t; ll x, y; cin >> s >> t >> x >> y; orig_s[i] = s; orig_t[i] = t; orig_x[i] = x; orig_y[i] = y; recq[i].id = i; recq[i].s = s; recq[i].t = t; recq[i].lca = lca(s, t); recq[i].y = y; } vector<RecQ*> vec; vec.reserve(q); for (int i = 0; i < q; i++) { vec.pb(&recq[i]); } fenw.init(n); ansIndex.assign(q, 0); solve_rec(0, m, vec); vector<int> order(q); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int a, int b){ return ansIndex[a] > ansIndex[b]; }); fenw.init(n); int ptr = m; vector<ll> finalCnt(q, 0); for (int idx : order) { int k = ansIndex[idx]; while (ptr > k) { int u = items[ptr].v; fenw.range_add(tin[u], tout[u], 1); ptr--; } int s = orig_s[idx], t = orig_t[idx]; int lc = lca(s, t); ll cntOnPath = fenw.point_get(tin[s]) + fenw.point_get(tin[t]) - 2 * fenw.point_get(tin[lc]); finalCnt[idx] = cntOnPath; } for (int i = 0; i < q; i++) { ll cnt = finalCnt[i]; ll res = orig_x[i] - cnt; if (res < 0) cout << -1 << "\n"; else cout << res << "\n"; } return 0; }

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:140:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |                 freopen(taskname".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:141:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |                 freopen(taskname".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...