제출 #872853

#제출 시각아이디문제언어결과실행 시간메모리
872853MinaRagy06Two Currencies (JOI23_currencies)C++17
30 / 100
1119 ms159160 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define mid ((l + r) >> 1) const int N = 100'005, inf = 1e18; int anc[N][17], st[N], en[N], t; ll h[N]; vector<array<int, 2>> adj[N]; array<ll, 2> a[N]; void dfs(int i, int par, ll d) { h[i] = d; anc[i][0] = par; for (int j = 1; j < 17; j++) { anc[i][j] = anc[anc[i][j - 1]][j - 1]; } st[i] = t++; for (auto [nxt, w] : adj[i]) { if (nxt == par) continue; dfs(nxt, i, d + w); } en[i] = t; } int getlca(int u, int v) { if (st[u] > st[v]) swap(u, v); if (st[u] <= st[v] && en[v] <= en[u]) { return u; } for (int j = 16; j >= 0; j--) { if (!(st[anc[u][j]] <= st[v] && en[v] <= en[anc[u][j]])) { u = anc[u][j]; } } return anc[u][0]; } struct node { ll val = 0; int cnt = 0; node(int x) { val = x, cnt = 1; } node() {} node& operator+=(node y) { val += y.val; cnt += y.cnt; return *this; } friend node operator+(node x, node y) { return x += y; } node& operator-=(node y) { val -= y.val; cnt -= y.cnt; return *this; } friend node operator-(node x, node y) { return x -= y; } node& operator*=(int x) { val *= x; cnt *= x; return *this; } friend node operator*(int x, node y) { return y *= x; } }; node lazy[1 << 18]; void upd(int i, int l, int r, int s, int e, node v) { if (s <= l && r <= e) { lazy[i] += v; return; } if (r < s || e < l) { return; } upd(i << 1, l, mid, s, e, v); upd(i << 1 | 1, mid + 1, r, s, e, v); } node get(int i, int l, int r, int x) { if (l == r) { return lazy[i]; } if (x <= mid) { return get(i << 1, l, mid, x) + lazy[i]; } else { return get(i << 1 | 1, mid + 1, r, x) + lazy[i]; } } int n, m, q; node height(int u) { return get(1, 0, n - 1, st[u]); } vector<array<ll, 7>> ask[2][N]; vector<array<ll, 5>> ansask[N]; int main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> n >> m >> q; array<int, 3> edges[n - 1]; for (int i = 0; i < n - 1; i++) { auto &[u, v, cnt] = edges[i]; cin >> u >> v; cnt = 0; } for (int i = 0; i < m; i++) { cin >> a[i][1] >> a[i][0]; a[i][1]--; edges[a[i][1]][2]++; } for (auto &[u, v, cnt] : edges) { adj[u].push_back({v, cnt}); adj[v].push_back({u, cnt}); } dfs(1, 1, 0); for (auto &[u, v, cnt] : edges) { if (st[u] > st[v]) { swap(u, v); } } sort(a, a + m); array<ll, 4> query[q]; for (int i = 0; i < q; i++) { auto &[u, v, x, y] = query[i]; cin >> u >> v >> y >> x; ask[0][m >> 1].push_back({u, v, x, y, 0, m, i}); } int cur = 0; for (int _ = 0; _ < 17; _++) { bool done = 0; for (int i = 0; i < (1 << 18); i++) { lazy[i] = node(); } for (int md = 0; md <= m; md++) { ask[cur ^ 1][md].clear(); } int idx = -1; for (int md = 0; md <= m; md++) { if (md && idx + 1 < m) { ll tar = a[idx + 1][0]; while (idx + 1 < m && a[idx + 1][0] == tar) { idx++; int e = a[idx][1]; int v = edges[e][1]; upd(1, 0, n - 1, st[v], en[v], a[idx][0]); } } for (auto &[u, v, x, y, l, r, qidx] : ask[cur][md]) { done = 1; int lca = getlca(u, v); node ttl = height(u) + height(v) - 2 * height(lca); if (ttl.val <= x) { l = md + 1; } else { r = md - 1; } if (l <= r) { ask[cur ^ 1][(l + r) >> 1].push_back({u, v, x, y, l, r, qidx}); } else { ansask[r].push_back({u, v, x, y, qidx}); } } } if (!done) break; cur ^= 1; } ll ans[q]; memset(ans, '?', sizeof ans); int idx = -1; for (int i = 0; i < (1 << 18); i++) { lazy[i] = node(); } for (int i = 0; i <= m; i++) { if (i && idx + 1 < m) { ll tar = a[idx + 1][0]; while (idx + 1 < m && a[idx + 1][0] == tar) { idx++; int e = a[idx][1]; int v = edges[e][1]; upd(1, 0, n - 1, st[v], en[v], a[idx][0]); } } for (auto &[u, v, x, y, qidx] : ansask[i]) { int lca = getlca(u, v); node ttl = height(u) + height(v) - 2 * height(lca); ll dist = h[u] + h[v] - 2 * h[lca]; x -= ttl.val; dist -= ttl.cnt; ll nxt = inf; if (idx + 1 < m) { nxt = a[idx + 1][0]; } ll rem = min((ll)dist, x / nxt); dist -= rem; y -= dist; ans[qidx] = y; } } for (int i = 0; i < q; i++) { if (ans[i] < 0) { cout << "-1\n"; } else { cout << ans[i] << '\n'; } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

currencies.cpp:6:30: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    6 | const int N = 100'005, inf = 1e18;
      |                              ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...