| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1045216 | TsotneSV | 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 <bits/stdc++.h>
using namespace std;
/* /\_/\
(= ._.)
/ > \>
*/
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define int long long
#define fi first
#define se second
#define pb push_back
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define dbg(x) cerr<<#x<<" "<<x<<endl
typedef long long ll;
typedef pair<int,int> pii;
const int lg=18,MAXN=1e5+5;
int n,m,q,timer=1,lev[MAXN],jmp[lg][MAXN],in[MAXN],out[MAXN];
pii edge[MAXN],cp[MAXN]; vector<int> g[MAXN];
struct Node {
Node *l = nullptr, *r = nullptr;
ll sum = 0; int cnt = 0;
Node(ll sum = 0,int f = 0) : l(nullptr),r(nullptr) {this->sum = sum,this->cnt = f;}
Node(Node *L,Node *R) {
this->l = L;
this->r = R;
sum = L->sum + R->sum;
cnt = L->cnt + R->cnt;
}
Node* getL() {
if (!l) l = new Node();
return l;
}
Node* getR() {
if (!r) r = new Node();
return r;
}
};
Node *root[MAXN];
Node* update(Node *node,int tl,int tr,int idx,ll val,int f = 0) {
if(tl == tr) {
return new Node(val,f);
}else {
int tm = (tl + tr)/2;
if(idx <= tm) return new Node(update(node->getL(),tl,tm,idx,val,f),node->getR());
else return new Node(node->getL(),update(node->getR(),tm+1,tr,idx,val,f));
}
}
pair<ll,int> query(Node *node,int tl,int tr,int l,int r) {
if(l > r) return {0,0};
if(tl == l and tr == r) return {node->sum,node->cnt};
else {
int tm = (tl + tr)/2;
auto p1 = query(node->getL(),tl,tm,l,min(r,tm)),p2 = query(node->getR(),tm+1,tr,max(l,tm+1),r);
return {p1.fi + p2.fi,p1.se + p2.se};
}
}
void dfs(int v,int p = 0) {
lev[v] = lev[p] + 1; in[v] = timer++;
jmp[0][v] = p;
for(int i=1;i<lg;i++) jmp[i][v] = jmp[i-1][jmp[i-1][v]];
for(int i : g[v]) {
if(i != p) dfs(i,v);
} out[v] = timer;
}
int lca(int u,int v) {
if(lev[u] < lev[v]) swap(u,v);
for(int i=lg-1;i>=0;i--) {
if(lev[jmp[i][u]] >= lev[v]) u = jmp[i][u];
}
if(u == v) return u;
for(int i=lg-1;i>=0;i--) {
if(jmp[i][u] != jmp[i][v]) {
u = jmp[i][u];
v = jmp[i][v];
}
}
return jmp[0][u];
}
void solve(){
cin>>n>>m>>q;
for(int i=1;i<=n-1;i++) {
int u,v; cin>>u>>v;
g[u].pb(v); g[v].pb(u);
edge[i] = {u,v};
}
lev[0] = 0;
for(int i=0;i<lg;i++) jmp[i][0] = 0;
dfs(1);
root[0] = new Node();
for(int i=1;i<=m;i++) cin>>cp[i].se>>cp[i].fi;
sort(cp+1,cp+m+1);
for(int i=1;i<=m;i++) {
int p = cp[i].se; ll c = cp[i].fi;
auto [u,v] = edge[p]; if(lev[u] < lev[v]) swap(u,v);
auto [a,b] = query(root[i-1],0,timer,in[u],in[u]);
c += a; int f1 = b,f2 = query(root[i-1],0,timer,out[u],out[u]).se;
root[i] = update(root[i-1],0,timer,in[u],c,f1+1);
root[i] = update(root[i],0,timer,out[u],-c,f2-1);
}
auto eval = [&](Node *r,int u,int v) {
int LCA = lca(u,v);
auto p1 = query(r,0,timer,0,in[u]),p2 = query(r,0,timer,0,in[v]),p3 = query(r,0,timer,0,in[LCA]);
return p1.fi + p2.fi - 2 * p3.fi;
};
/* for(int i=1;i<=n;i++) {
cout<<i<<" "<<in[i]<<" "<<out[i]<<endl;
} */
while(q--) {
int u,v,g; ll s;
cin>>u>>v>>g>>s;
int l = 0,r = m,tg = 0;
while(l <= r) {
int mid = (l + r)/2;
if(eval(root[mid],u,v) <= s) {
tg = mid;
l = mid + 1;
}else {
r = mid - 1;
}
}
int a = query(root[m],0,timer,0,in[u]).se + query(root[m],0,timer,0,in[v]).se - 2 * query(root[m],0,timer,0,in[lca(u,v)]).se;
int b = query(root[tg],0,timer,0,in[u]).se + query(root[tg],0,timer,0,in[v]).se - 2 * query(root[tg],0,timer,0,in[lca(u,v)]).se;
a -= b;
cout<<max(-1,g - a)<<endl;
}
}
signed main(){
send help
solve();
}