제출 #908612

#제출 시각아이디문제언어결과실행 시간메모리
908612vjudge1Two Currencies (JOI23_currencies)C++17
100 / 100
4169 ms270440 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll const int N = 100000 + 7; const int K = 20; int n; int m; int q; vector<int> g[N]; pair<int, int> edges[N]; int dep[N]; int par[N]; int l[N]; int r[N]; int tab[K][N]; int tt = 0; int sub[N]; pair<int, int> updates[N]; void build(int a, int p = 0) { l[a] = ++tt; tab[0][a] = p; for (int k = 1; k < K; k++) { tab[k][a] = tab[k - 1][tab[k - 1][a]]; } sub[a] = 1; for (auto &b : g[a]) { if (b != p) { par[b] = a; dep[b] = dep[a] + 1; build(b, a); sub[a] += sub[b]; } } r[a] = tt; } int lca(int x, int y) { if (dep[x] < dep[y]) { swap(x, y); } for (int k = K - 1; k >= 0; k--) { if (dep[x] - (1 << k) >= dep[y]) { x = tab[k][x]; } } if (x == y) { return x; } for (int k = K - 1; k >= 0; k--) { if (tab[k][x] != tab[k][y]) { x = tab[k][x]; y = tab[k][y]; } } return tab[0][x]; } bool is_ancestor(int x, int y) { /// x ancestor of y return l[x] <= l[y] && r[y] <= r[x]; } struct PST{ struct Node { int result; Node* left; Node* right; Node (int val = 0) { result = val; left = right = nullptr; } void refresh() { this->result = this->left->result + this->right->result; } }; Node* build(int from, int to) { Node *node = new Node(0); if (from < to) { int mid = (from + to) / 2; node->left = build(from, mid); node->right = build(mid + 1, to); } return node; } Node* initialize(int n) { return build(1, n); } Node* update(Node* base, int from, int to, int x, int val) { if (from < to) { int mid = (from + to) / 2; Node* newNode = new Node(); (*newNode) = (*base); if (x <= mid) { newNode->left = update(base->left, from, mid, x, val); } else { newNode->right = update(base->right, mid + 1, to, x, val); } newNode->refresh(); return newNode; } else { return (new Node(base->result + val)); } } int query(Node* node, int from, int to, int x, int y) { assert(from <= x && x <= y && y <= to); if (from == x && to == y) { return node->result; } else { int mid = (from + to) / 2; if (x <= mid && y <= mid) { return query(node->left, from, mid, x, y); } else if (mid + 1 <= x && mid + 1 <= y) { return query(node->right, mid + 1, to, x, y); } else { return query(node->left, from, mid,x , mid) + query(node->right, mid + 1, to, mid + 1, y); } } } Node* version[N]; int n; void buildVersions(int n_) { n = n_; Node* part = initialize(n); version[0] = part; for(int i = 1; i <= m; i++) { int val = updates[i].first; int x = updates[i].second; part = update(part, 1, n, l[x], +val); if (r[x] + 1 <= n) { part = update(part, 1, n, r[x] + 1, -val); } version[i] = part; } } int sum(int when, int x) { return query(version[when], 1, n, 1, l[x]); } int get_sum(int when, int x, int y) { int z = lca(x, y); return sum(when, x) + sum(when, y) - 2 * sum(when, z); } }; PST tree1, tree2; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); /// freopen("input.txt", "r", stdin); cin >> n >> m >> q; for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); edges[i] = {x, y}; } build(1); for (int i = 1; i <= m; i++) { ll road, val; cin >> road >> val; int x = edges[road].first; int y = edges[road].second; if (dep[x] < dep[y]) { swap(x, y); } updates[i] = {val, x}; } sort(updates + 1, updates + m + 1); tree1.buildVersions(n); for (int i = 1; i <= m; i++) { updates[i].first = 1; } tree2.buildVersions(n); while (q--) { ll s, t, x, y; cin >> s >> t >> x >> y; int low = 1, high = m, sol = 0; while (low <= high) { int mid = (low + high) / 2; if (tree1.get_sum(mid, s, t) <= y) { sol = mid; low = mid + 1; } else { high = mid - 1; } } int z = lca(s, t); int payed = tree2.get_sum(sol, s, t); int total = tree2.get_sum(m, s, t); int keep = x - (total - payed); if (keep < 0) { keep = -1; } cout << keep << "\n"; } return 0; }

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

currencies.cpp: In function 'int main()':
currencies.cpp:206:9: warning: unused variable 'z' [-Wunused-variable]
  206 |     int z = lca(s, t);
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...