Submission #803029

#TimeUsernameProblemLanguageResultExecution timeMemory
803029lukameladzeTwo Currencies (JOI23_currencies)C++17
0 / 100
10 ms8648 KiB
# include <bits/stdc++.h> using namespace std; #define f first #define s second #define pii pair <int, int> #define pb push_back const int N = 3e5 + 5; int n, m, q, a[N], b[N], edge[N], par[N][20], idx[N], c[N], in[N], out[N], tin, cur; vector <pii> v[N]; int le_[30 * N], ri_[30 * N], root[N]; pii tree[30 * N]; void dfs(int a, int p) { par[a][0] = p; for (int i = 1; i <= 18; i++) { par[a][i] = par[par[a][i - 1]][i - 1]; } in[a] = ++tin; for (pii sth : v[a]) { int to = sth.f, id = sth.s; if (to == p) continue; edge[id] = to; // {a, to} dfs(to, a); } out[a] = tin; } int upper(int a, int b) { return (in[a] <= in[b] && out[a] >= out[b]); } int lca(int a, int b) { if (upper(a, b)) return a; for (int i = 18; i >= 0; i--) { if (par[a][i] && !upper(par[a][i], b)) a = par[a][i]; } return par[a][0]; } pii merge(pii a, pii b) { return {a.f + b.f, a.s + b.s}; } void build(int node, int le, int ri) { if (le == ri) { tree[node] = {0, 0}; return ; } int mid = (le + ri) / 2; le_[node] = ++cur; ri_[node] = ++cur; build(le_[node], le, mid); build(ri_[node], mid + 1, ri); tree[node] = merge(tree[le_[node]], tree[ri_[node]]); } void update(int node, int le, int ri, int idx, int val) { if (le > idx || ri < idx) return ; if (le == ri) { tree[cur] = {tree[node].f + val, tree[node].s + ((val > 0) ? 1 : -1)}; return ; } int mid = (le + ri) / 2; int x = cur; le_[x] = le_[node]; ri_[x] = ri_[node]; if (idx <= mid) le_[x] = ++cur; else ri_[x] = ++cur; update(le_[node], le, mid, idx, val); // node update(ri_[node], mid + 1, ri, idx, val); //node tree[x] = merge(tree[le_[x]], tree[ri_[x]]); } pii getans(int node, int le, int ri, int start, int end) { if (le > end || ri < start) return {0, 0}; if (le >= start && ri <= end) return tree[node]; int mid = (le + ri) / 2; return merge(getans(le_[node], le, mid, start, end), getans(ri_[node], mid + 1, ri, start, end)); } signed main() { cin>>n>>m>>q; for (int i = 1; i <= n - 1; i++) { cin>>a[i]>>b[i]; v[a[i]].pb({b[i], i}); v[b[i]].pb({a[i], i}); } dfs(1, 0); vector <pii> vec; for (int i = 1; i <= m; i++) { cin>>idx[i]>>c[i]; idx[i] = edge[idx[i]]; // {a, to} vec.pb({c[i], idx[i]}); } vec.pb({0, 0}); sort(vec.begin(), vec.end()); root[0] = 1; cur = 1; build(1, 1, n); for (int i = 1; i < (int)vec.size(); i++) { root[i] = ++cur; //cout<<"update "<<in[vec[i].s]<<" "<<out[vec[i].s]<<" "<<vec[i].f<<"\n"; update(root[i - 1], 1, n, in[vec[i].s], vec[i].f); int proot = root[i]; if (out[vec[i].s] + 1 <= n) { root[i] = ++cur; update(proot, 1, n, out[vec[i].s] + 1, -vec[i].f); } /* for (int j = 1; j <= n; j++) { cout<<getans(root[i], 1, n, 1, in[j]).s<<" "; } cout<<"\n"; */ } while (q--) { int s, t, x, y; cin>>s>>t>>x>>y; int lc = lca(s, t); int l = 0, r = (int)vec.size() - 1, ans = -1; while (l <= r) { int mid = (l + r) / 2; int silver = getans(root[mid], 1, n, 1, in[s]).f + getans(root[mid], 1, n, 1, in[t]).f - 2 * getans(root[mid], 1, n, 1, in[lc]).f; if (silver <= y) { ans = mid; l = mid + 1; } else r = mid - 1; } if (ans == (int)vec.size() - 1) { cout<<x<<"\n"; continue; } int sz = (int)vec.size() - 1; int rem = getans(root[sz], 1, n, 1, in[s]).s + getans(root[sz], 1, n, 1, in[t]).s - 2 * getans(root[sz], 1,n, 1, in[lc]).s; rem -= (getans(root[ans], 1, n, 1, in[s]).s + getans(root[ans], 1, n, 1, in[t]).s - 2 * getans(root[ans], 1, n, 1, in[lc]).s); if (rem > x) cout<<-1<<"\n"; else cout<<(x - rem)<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...