| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1086630 | Tozzyyyy | Two Currencies (JOI23_currencies) | C++14 | 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.
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2,fma,bmi")
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long , long long>
#define fi first
#define se second
#define bit(i,j) ((j >> i) & 1)
#define lowbit(x) (x&(-x))
using namespace std;
const long long inf = 1e18+1;
const int mod = 998244353;
const int MAXN = 1e5+100;
#define ll long long
struct Fen{
ll A[MAXN], B[MAXN], n;
ll sum(ll x) {
ll ans = 0;
for(int i = x ; i > 0 ; i -= lowbit(i)) ans += B[i];
return ans;
}
void update(int l, int r, ll v) {
upd(r + 1, -v); upd(l, v);
}
void init(int _n) {
n = _n;
fill(B, B + n + 1, 0); A[0] = 0;
for(int i = 1 ; i <= n ; ++i) upd(i, A[i] - A[i - 1]);
}
};
struct query{
long long remain , y;
int s , t , p , x , l , r , m , ans , c;
pll res , T;
};
vector<pair<int , vector<int>>> adj[MAXN];
int h[MAXN] , up[MAXN][18];
void pre_dfs(int u){
for(auto [v , w] : adj[u]){
if(v == up[u][0]) continue;
up[v][0] = u;
for(int i = 1 ; i <= 17 ; i ++){
up[v][i] = up[up[v][i-1]][i-1];
}
h[v] = h[u] + 1;
pre_dfs(v);
}
}
int lca(int u , int v){
if(h[u] != h[v]){
if(h[u] < h[v]) swap(u , v);
int k = h[u] - h[v];
for(int i = 0 ; i <= 17 ; i ++){
if(bit(i , k)) u = up[u][i];
}
}
if(u == v) return v;
for(int i = 17 ; i >= 0 ; i --){
if(up[u][i] != up[v][i]){
u = up[u][i] ; v = up[v][i];
}
}
return up[u][0];
}
struct node{
int x , t , id;
};
vector<node> v[MAXN];
Fen Bit1 , Bit2;
int m;
query Q[MAXN];
int cnt[MAXN];
void dfs(int u , const vector<int> &a ){
for(auto [x , t , id] : v[u]){
Q[id].res.se += cnt[x];
Q[id].res.fi += Bit1.sum(x) * t;
Q[id].c += Bit2.sum(x) * t;
}
if(v[u].size()) v[u].clear();
for(auto [v , W] : adj[u]){
if(v == up[u][0]) continue;
vector<int> id(W.size());
int jj = 0 , l;
for(auto w : W){
id[jj] = lower_bound(a.begin() , a.end() , w) - a.begin() + 1;
l = id[jj];
jj++;
if(a[l] == w) cnt[l]++;
if(l >= 2) Bit2.update(1 , l - 1 , 1);
if(l <= a.size()) Bit1.update(l, a.size() , w);
}
dfs(v , a);
jj = 0;
for(auto w : W){
l = id[jj++];
if(a[l] == w) cnt[l]--;
if(l >= 2) Bit2.update(1 , l - 1 , -1);
if(l <= a.size()) Bit1.update(l, a.size() , -w);
}
}
}
vector<int> check[MAXN];
int32_t main(){
//freopen("LAURA.inp", "r", stdin);
//freopen("LAURA.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n , q; cin >> n >> m >> q;
vector<pll> E(n);
for(int i = 1 ; i < n ; i++){
cin >> E[i].fi >> E[i].se;
}
for(int i = 1 ; i <= m ; i++){
int p , c; cin >> p >> c;
check[p].push_back(c);
}
for(int i = 1 ; i < n ; i++){
adj[E[i].fi].push_back({E[i].se , check[i]});
adj[E[i].se].push_back({E[i].fi , check[i]});
}
Bit1.init(q); Bit2.init(q);
pre_dfs(1);
for(int i = 1 ; i <= q ; i++){
cin >> Q[i].s >> Q[i].t >> Q[i].x >> Q[i].y;
Q[i].l = 0, Q[i].r = 1e9;
Q[i].ans = -1;
Q[i].p = lca(Q[i].s , Q[i].t);
}
while(1){
bool flag = 0;
vector<int> event , a;
for(int i = 1 ; i <= q ; i++){
if(Q[i].l <= Q[i].r){
Q[i].m = (Q[i].l + Q[i].r) >> 1;
event.push_back(Q[i].m);
a.push_back(i);
flag = 1;
Q[i].res = {0 , 0}; Q[i].c = 0;
}
}
if(flag == 0) break;
sort(all(event));
for(auto x : a){
int i = lower_bound(all(event) , Q[x].m) - event.begin();
v[Q[x].s].push_back({i + 1 , 1 , x});
v[Q[x].t].push_back({i + 1, 1 , x});
v[Q[x].p].push_back({i + 1, -2 , x});
}
dfs(1 , event);
for(auto x : a){
if(Q[x].res.fi <= Q[x].y){
Q[x].remain = Q[x].y - Q[x].res.fi;
Q[x].ans = Q[x].c ; Q[x].l = Q[x].m + 1;
}else{
Q[x].T = {Q[x].m , Q[x].res.se};
Q[x].r = Q[x].m - 1;
}
}
}
for(int i = 1 ; i <= q ; i++){
if(Q[i].T.fi != 0){
Q[i].ans -= min(Q[i].T.se , Q[i].remain / Q[i].T.fi);
}
cout << (Q[i].x - Q[i].ans >= 0 ? Q[i].x - Q[i].ans : -1) << "\n";;
}
return 0;
}