| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1086614 | 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,unroll-loops")
#pragma GCC target("arch=skylake")
#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)
using namespace std;
const long long inf = 1e18+1;
const int mod = 998244353;
const int MAXN = 2e5+100;
#define int long long
#define ll long long
struct Fen{
int n;
vector<ll>bit1, bit2;
void init(ll _n){
n = _n + 10;
bit1.clear(); bit2.clear();
bit1.resize(_n + 10, 0), bit2.resize(_n + 10 , 0);
};
void updatePoint(vector<ll>& b, int u, ll v) {
int idx = u;
while (idx <= n) {
b[idx] = (b[idx] + v);
idx += (idx & (-idx));
}
}
void updateRange(int l, int r, ll v) {
updatePoint(bit1, l, ((n - l + 1) * v));
updatePoint(bit1, r + 1, (-(n - r) * v));
updatePoint(bit2, l, v);
updatePoint(bit2, r + 1, -v);
}
ll getSum(vector<ll>& b, ll u) {
ll idx = u, ans = 0;
while (idx > 0) {
ans = (ans + b[idx]);
idx -= (idx & (-idx));
}
return ans;
}
ll prefixSum(ll u) {
ll x = (getSum(bit1, u) - (getSum(bit2, u) * (n - u)));
return x;
}
ll rangeSum(int l, int r) {
ll x = (prefixSum(r) - prefixSum(l - 1));
return x;
}
};
struct query{
int remain , s , t , p , x , y , 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.rangeSum(x , x) * t;
Q[id].c += Bit2.rangeSum(x , x) * t;
}
for(auto [v , W] : adj[u]){
if(v == up[u][0]) continue;
for(auto w : W){
int l = lower_bound(a.begin() , a.end() , w) - a.begin() + 1;
if(a[l] == w) cnt[l]++;
if(l >= 2) Bit2.updateRange(1 , l - 1 , 1);
if(l <= a.size()) Bit1.updateRange(l, a.size() , w);
}
dfs(v , a);
for(auto w : W){
int l = lower_bound(a.begin() , a.end() , w) - a.begin() + 1;
if(a[l] == w) cnt[l]--;
if(l >= 2) Bit2.updateRange(1 , l - 1 , -1);
if(l <= a.size()) Bit1.updateRange(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){
v[Q[x].s].clear();
v[Q[x].t].clear();
v[Q[x].p].clear();
}
for(int i =1 ; i<= a.size() ;i ++) cnt[i] = 0;
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;
}