| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 893213 | VerdantGMD | Two Currencies (JOI23_currencies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>#include <bits/stdc++.h>using namespace std;int n, m, q;vector<pair<int, int> > tab[100005];vector<pair<int, int> > adds;vector<int> mids[100005];struct query{ int l; int r; int mid; int lca; int a; int b; int gold; int wyn; long long silver; int coinsatloss = 0;};vector<query> queries;int jp[100005][21];int checked[100006];int timee = 1;int preorder[100005];int postorder[100005];pair<long long, int> tree[500005];int base;int vfe[100005];void dfs(int p, int parent){ preorder[p] = timee; timee++; for(int i = 0; i < tab[p].size(); i++) { if(tab[p][i].first != parent) { vfe[tab[p][i].second] = tab[p][i].first; checked[tab[p][i].first] = checked[p] + 1; jp[tab[p][i].first][0] = p; for(int o = 1; (1 << o) <= checked[tab[p][i].first]; o++) { jp[tab[p][i].first][o] = jp[ jp[tab[p][i].first] [o-1] ][o - 1]; } dfs(tab[p][i].first, p); } } postorder[p] = timee; timee++;}void upd(int a, int val, int add){ a += base; tree[a].first += val; tree[a].second += add; a/=2; while(a != 0) { tree[a].first = tree[a*2].first + tree[a*2+1].first; tree[a].second = tree[a*2].second + tree[a*2+1].second; a/=2; }}long long treequery(int a, int b){ a += base - 1; b += base + 1; long long res = 0 ; while(a/2 != b/2) { if(a % 2 == 0) { res += tree[a+1].first; } if(b % 2 == 1) { res += tree[b-1].first; } a/=2; b/=2; } return res;}int treequeryamount(int a, int b){ a += base - 1; b += base + 1; int res = 0 ; while(a/2 != b/2) { if(a % 2 == 0) { res += tree[a+1].second; } if(b % 2 == 1) { res += tree[b-1].second; } a/=2; b/=2; } return res;}int LCA(int a, int b){ if(checked[b] > checked[a]) { swap(a, b); } for(int i = 20; i >= 0; i--) { if(checked[a] - checked[b] >= (1 << i)) { a = jp[a][i]; } } if(a == b) { return a; } for(int i = 20; i >= 0; i--) { if(jp[a][i] != jp[b][i]) { a = jp[a][i]; b = jp[b][i]; } } return jp[a][0];}void superbinsearch(){ int leftt = q; while (leftt > 0) { for(int i = 0; i < m; i++) { upd(preorder[vfe[adds[i].second]], adds[i].first, 1); upd(postorder[vfe[adds[i].second]], -adds[i].first, -1); for(int qnum : mids[i]) { long long wyn = 0; int a = queries[qnum].a; int b = queries[qnum].b; if(checked[a] < checked[b]) { swap(a, b); } wyn += treequery(preorder[queries[qnum].lca], preorder[a]); wyn -= tree[preorder[queries[qnum].lca] + base].first; if(b != queries[qnum].lca) { wyn += treequery(preorder[queries[qnum].lca], preorder[b]); wyn -= tree[preorder[queries[qnum].lca] + base].first; } //cout << "mid" << i << " qnum" << qnum << " wyn" << wyn << endl; if(wyn > queries[qnum].silver) { queries[qnum].r = queries[qnum].mid - 1; } else { queries[qnum].l = queries[qnum].mid + 1; } if(queries[qnum].r < queries[qnum].l) { leftt--; queries[qnum].wyn = queries[qnum].r; } else { queries[qnum].mid = (queries[qnum].l + queries[qnum].r)/2; mids[queries[qnum].mid].push_back(qnum); } } mids[i].clear(); } for(int i = 0; i < 2*n + base + 1000; i++) { tree[i].first = 0; tree[i].second = 0; } }}int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> q; base = 2 * n; for(int i = 1; i <= n-1; i++) { int a, b; cin >> a >> b; tab[a].push_back({b, i}); tab[b].push_back({a, i}); } dfs(1, 1); for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; adds.push_back({b, a}); } for(int i = 0; i < q; i++) { int a, b, c; long long d; cin >> a >> b >> c >> d; query que; que.a = a; que.b = b; que.gold = c; que.silver = d; que.l = 0; que.r = m-1; que.mid = (m-1)/2; que.lca = LCA(a, b); mids[que.mid].push_back(i); queries.push_back(que); } sort(adds.begin(), adds.end()); superbinsearch(); for(int i = 0; i < q; i++) { mids[queries[i].wyn].push_back(i); } for(int i = 0; i < m; i++) { upd(preorder[vfe[adds[i].second]], adds[i].first, 1); upd(postorder[vfe[adds[i].second]], -adds[i].first, -1); for(int qnum : mids[i]) { int wyn = 0; int a = queries[qnum].a; int b = queries[qnum].b; if(checked[a] < checked[b]) { swap(a, b); } wyn += treequeryamount(preorder[queries[qnum].lca], preorder[a]); wyn -= tree[preorder[queries[qnum].lca] + base].second; if(b != queries[qnum].lca) { wyn += treequeryamount(preorder[queries[qnum].lca], preorder[b]); wyn -= tree[preorder[queries[qnum].lca] + base].second; } queries[qnum].coinsatloss = wyn; } mids[i].clear(); } for(int i = 0; i < q; i++) { int wyn = 0; int a = queries[i].a; int b = queries[i].b; if(checked[a] < checked[b]) { swap(a, b); } wyn += treequeryamount(preorder[queries[i].lca], preorder[a]); wyn -= tree[preorder[queries[i].lca] + base].second; if(b != queries[i].lca) { wyn += treequeryamount(preorder[queries[i].lca], preorder[b]); wyn -= tree[preorder[queries[i].lca] + base].second; } // cout << "wyn " << wyn << " buyable " << queries[i].coinsatloss << endl; cout << max(-1, queries[i].gold - wyn + queries[i].coinsatloss) << endl; }}