| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1124663 | Tyx2019 | Two Currencies (JOI23_currencies) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
#define debug(x) if(0) cout << #x << " is " << x << endl;
using namespace std;
int N, M, Q;
struct node{
int S, E, M, V, ladd;
node *l, *r;
//range add, point query
node(int _S, int _E, int _V = 0, int _ladd = 0){
S = _S;
E = _E;
V = _V;
ladd = _ladd;
l = r = NULL;
M = (S + E) >> 1;
}
node(node *other){
S = other->S;
E = other->E;
V = other->V;
ladd = other->V;
l = other->l;
r = other->r;
M = other->M;
}
void prop(){
if(S == E) return;
if(!l){
l = new node(S, M);
r = new node(M + 1, E);
}
else{
node *cpyl = new node(l);
cpyl->S = l->S;
cpyl->E = l->E;
cpyl->M = l->M;
cpyl->V = l->V;
cpyl->ladd = l->ladd;
cpyl->l = l->l;
cpyl->r = l->r;
l = cpyl;
node *cpyr = new node(r);
cpyr->S = r->S;
cpyr->E = r->E;
cpyr->M = r->M;
cpyr->V = r->V;
cpyr->ladd = r->ladd;
cpyr->l = r->l;
cpyr->r = r->r;
r = cpyr;
}
if(ladd != 0){
l->V += (M - S + 1) * ladd;
r->V += (E - M) * ladd;
l->ladd += ladd;
r->ladd += ladd;
ladd = 0;
}
}
int query(int x){
prop();
if(S == E) return V;
if(x <= M) return l->query(x);
else return r->query(x);
}
node* upd(int start, int end, int val){
prop();
if(start == S && end == E){
node *cpy = new node(S, E, V + (E - S + 1) * val, ladd + val);
cpy->l = l;
cpy->r = r;
return cpy;
}
else if(end <= M){
l->upd(start, end, val);
node* cpy = new node(S, E, cpyl->V + r->V, ladd);
cpy->l = cpyl;
cpy->r = r;
return cpy;
}
else if(start > M){
r->upd(start, end, val);
node* cpy = new node(S, E, cpyr->V + l->V, ladd);
cpy->l = l;
cpy->r = cpyr;
return cpy;
}
else{
l->upd(start, M, val);
r->upd(M + 1, end, val);
node* cpy = new node(S, E, cpyl->V + cpyr->V, ladd);
cpy->l = cpyl;
cpy->r = cpyr;
return cpy;
}
}
}*seggssum, *seggscnt;
const int maxN = 1e5 + 5;
vector<int> adj[maxN];
int order[maxN];
int cur = 0;
int mem[maxN][20];
int depth[maxN];
int streesz[maxN];
void dfs(int x, int par){
order[x] = cur++;
mem[x][0] = par;
streesz[x] = 1;
for(auto j:adj[x]){
if(j == par) continue;
depth[j] = depth[x] + 1;
dfs(j, x);
streesz[x] += streesz[j];
}
}
int anc(int x, int k){
int cur = x;
for(int i=19;i>=0;i--){
if(((1 << i) & k) != 0){
cur = mem[cur][i];
}
}
return cur;
}
int lcaa(int x, int y){
if(depth[x] < depth[y]) swap(x, y);
int k = depth[x] - depth[y];
x = anc(x, k);
assert(min(x, y) >= 1);
assert(k >= 0);
if(x == y) return x;
for(int i=19;i>=0;i--){
if(mem[x][i] != mem[y][i]){
x = mem[x][i];
y = mem[y][i];
}
}
return mem[x][0];
}
main(){
cin >> N >> M >> Q;
seggssum = new node(0, N + 5);
seggscnt = new node(0, N + 5);
int A[N], B[N];
for(int i=1;i<=N-1;i++) cin >> A[i] >> B[i];
for(int i=1;i<=N-1;i++){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
depth[1] = 0;
dfs(1, -1);
//2k
for(int j=1;j<20;j++){
for(int i=1;i<=N;i++){
int hpar = mem[i][j-1];
if(hpar == -1) mem[i][j] = -1;
else mem[i][j] = mem[hpar][j-1];
}
}
int C[M], P[M];
for(int i=0;i<M;i++){
cin >> P[i] >> C[i];
}
int S[Q], T[Q], X[Q], Y[Q], lca[Q];
for(int i=0;i<Q;i++){
cin >> S[i] >> T[i] >> X[i] >> Y[i];
lca[i] = lcaa(S[i], T[i]);
}
vector<pair<int, int>> V;
for(int i=0;i<M;i++){
V.push_back({C[i], P[i]});
}
sort(V.begin(), V.end());
node* sum[M + 5];
node* count[M + 5];
sum[0] = seggssum;
count[0] = seggscnt;
for(int i=1;i<=M;i++){
int x = V[i-1].second;
int bruh = A[x];
if(depth[B[x]] >= depth[bruh]) bruh = B[x];
sum[i] = sum[i-1]->upd(order[bruh], order[bruh] + streesz[bruh] - 1, V[i-1].first);
count[i] = count[i-1]->upd(order[bruh], order[bruh] + streesz[bruh] - 1, 1);
}
debug("hi");
for(int i=0;i<Q;i++){
int lb = 0;
int ub = M;
while(ub > lb){
int m = (ub + lb + 1) >> 1;
int s = sum[m]->query(order[S[i]]);
int t = sum[m]->query(order[T[i]]);
int l = sum[m]->query(order[lca[i]]);
if((s + t - (2 * l)) <= Y[i]) lb = m;
else ub = m - 1;
}
debug(sum[2]->query(order[S[i]]));
debug(sum[2]->query(order[T[i]]));
debug(sum[2]->query(order[lca[i]]));
int s = count[lb]->query(order[S[i]]);
int t = count[lb]->query(order[T[i]]);
int l = count[lb]->query(order[lca[i]]);
int k = s + t - (2 * l);
debug(s);
debug(t);
debug(l);
debug(lca[i]);
s = count[M]->query(order[S[i]]);
t = count[M]->query(order[T[i]]);
l = count[M]->query(order[lca[i]]);
debug(lb);
int tot = s + t - (2 * l);
debug(tot);
int nec = tot - k;
int res = X[i] - nec;
if(res < 0){
cout << "-1\n";
}
else cout << res << '\n';
}
for(int i=1;i<=N;i++) debug(order[i]);
}