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;
}
Compilation message (stderr)
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from currencies.cpp:3:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'arch=skylake' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
73 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
74 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
75 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
76 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
77 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'arch=skylake' was already specified in 'target' attribute
91 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'arch=skylake' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'arch=skylake' was already specified in 'target' attribute
101 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'arch=skylake' was already specified in 'target' attribute
currencies.cpp: In function 'void pre_dfs(long long int)':
currencies.cpp:65:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
65 | for(auto [v , w] : adj[u]){
| ^
currencies.cpp: In function 'void dfs(long long int, const std::vector<long long int>&)':
currencies.cpp:105:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
105 | for(auto [x , t , id] : v[u]){
| ^
currencies.cpp:110:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
110 | for(auto [v , W] : adj[u]){
| ^
currencies.cpp:116:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | if(l <= a.size()) Bit1.updateRange(l, a.size() , w);
| ~~^~~~~~~~~~~
currencies.cpp:123:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | if(l <= a.size()) Bit1.updateRange(l, a.size() , -w);
| ~~^~~~~~~~~~~
currencies.cpp: In function 'int32_t main()':
currencies.cpp:185:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
185 | for(int i =1 ; i<= a.size() ;i ++) cnt[i] = 0;
| ~^~~~~~~~~~~