// created by Dinh Manh Hung
// onepunchac168
// THPT CHUYEN HA TINH
// HA TINH, VIET NAM
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
//#pragma GCC target("sse4,avx2,fma")
#define task ""
#define ldb long double
#define pb push_back
#define fi first
#define se second
#define pc pop_back()
#define all(x) begin(x),end(x)
#define uniquev(v) v.resize(unique(all(v))-v.begin())
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define cntbit(v) __builtin_popcountll(v)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((1LL*a*b)/__gcd(a,b))
#define mask(x) (1LL<<(x))
#define readbit(x,i) ((x>>i)&1)
#define ins insert
typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;
ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};
const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const int maxn=1e6+5;
const int mod=1e9+7;
const char nl = '\n';
inline int ReadInt()
{
char co;
for (co = getchar(); co < '0' || co > '9'; co = getchar());
int xo = co - '0';
for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
xo = xo * 10 + co - '0';
return xo;
}
void WriteInt(int xo)
{
if (xo > 9)
WriteInt(xo / 10);
putchar(xo % 10 + '0');
}
/* END OF TEMPLATE*/
// ================= Solution =================//
const int N=1e5+5;
ll n,m,k;
vector <ll> vt[N];
ll p[N],c[N];
vector <ll> opt;
struct Node {
int left,right;
ll val;
ll vala;
Node(int left,int right,ll val,ll vala){
this->left=left;
this->right=right;
this->val=val;
this->vala=vala;
}
Node(){
}
} T[N*24+5];
int ver[N];
vector <ll> tmp[N];
int Nnode=0;
int update(int oldnode,int l,int r,int u,ll val)
{
if (l==r)
{
Nnode++;
T[Nnode]=Node(0,0,val,val*opt[r-1]);
return Nnode;
}
int mid=(l+r)/2;
Nnode++;
int newnode=Nnode;
if (u<=mid)
{
T[newnode].left=update(T[oldnode].left,l,mid,u,val);
T[newnode].right=T[oldnode].right;
T[newnode].val=T[T[newnode].left].val+T[T[newnode].right].val;
T[newnode].vala=T[T[newnode].left].vala+T[T[newnode].right].vala;
}
else
{
T[newnode].right=update(T[oldnode].right,mid+1,r,u,val);
T[newnode].left=T[oldnode].left;
T[newnode].val=T[T[newnode].left].val+T[T[newnode].right].val;
T[newnode].vala=T[T[newnode].left].vala+T[T[newnode].right].vala;
}
return newnode;
}
ll query(int node,int l,int r,int u,int v)
{
if (l>v||r<u)
{
return 0;
}
if (l>=u&&r<=v)
{
return T[node].val;
}
int mid=(l+r)/2;
ll a1=query(T[node].left,l,mid,u,v);
ll a2=query(T[node].right,mid+1,r,u,v);
return a1+a2;
}
ll querya(int node,int l,int r,int u,int v)
{
if (l>v||r<u)
{
return 0;
}
if (l>=u&&r<=v)
{
return T[node].vala;
}
int mid=(l+r)/2;
ll a1=querya(T[node].left,l,mid,u,v);
ll a2=querya(T[node].right,mid+1,r,u,v);
return a1+a2;
}
map<ii,ll> mp;
ll cha[N][25];
ll sz[N];
void dfs(int u,int vv)
{
for (auto v:vt[u])
{
if (v==vv)
{
continue;
}
cha[v][0]=u;
sz[v]=sz[u]+1;
for (int i=1;i<=20;i++)
{
cha[v][i]=cha[cha[v][i-1]][i-1];
}
dfs(v,u);
}
}
void dfs1(int u,int vv)
{
ver[u]=ver[vv];
for (auto v:tmp[u])
{
ll aa=lower_bound(opt.begin(),opt.end(),v)-opt.begin()+1;
ll bb=query(ver[u],1,opt.size(),aa,aa);
ver[u]=update(ver[u],1,opt.size(),aa,bb+1);
}
for (auto v:vt[u])
{
if (v==vv)
{
continue;
}
dfs1(v,u);
}
}
ll lca(int u,int v)
{
if (sz[u]>sz[v]){swap(u,v);}
for (int i=20;i>=0;i--)
{
if (sz[v]-mask(i)>=sz[u])
{
v=cha[v][i];
}
}
if (u==v){return u;}
for (int i=20;i>=0;i--)
{
if (cha[u][i]!=cha[v][i])
{
u=cha[u][i];
v=cha[v][i];
}
}
if (u!=v)
{
u=cha[u][0];
v=cha[v][0];
}
return u;
}
ll ua[N],va[N];
void optmushnpr()
{
cin>>n>>m>>k;
T[0]=Node(0,0,0,0);
ver[0]=0;
for (int i=1;i<n;i++)
{
cin>>ua[i]>>va[i];
vt[ua[i]].pb(va[i]);
vt[va[i]].pb(ua[i]);
}
dfs(1,0);
for (int i=1;i<=m;i++)
{
cin>>p[i]>>c[i];
ll id=p[i];
if (sz[ua[id]]>sz[va[id]])
{
tmp[ua[id]].pb(c[i]);
}
else
{
tmp[va[id]].pb(c[i]);
}
opt.pb(c[i]);
}
sort (opt.begin(),opt.end());
uniquev(opt);
dfs1(1,0);
while (k--)
{
ll x,y,u,v;
cin>>u>>v>>x>>y;
ll left=1;ll right=opt.size();
ll parent=lca(u,v);
ll ans=opt.size();
ll sum=querya(ver[u],1,opt.size(),1,opt.size())+querya(ver[v],1,opt.size(),1,opt.size())-2*querya(ver[parent],1,opt.size(),1,opt.size());
while (left<=right)
{
ll mid=(left+right)/2;
ll a1=querya(ver[u],1,opt.size(),1,mid);
ll a2=querya(ver[v],1,opt.size(),1,mid);
ll a3=querya(ver[parent],1,opt.size(),1,mid);
if (a1+a2-2*a3>=y)
{
sum=a1+a2-2*a3;
ans=mid;
right=mid-1;
}
else left=mid+1;
}
ll ok=0;
if (ans!=0)
{
if (sum>y)
{
ll h=(sum-y)/opt[ans-1];
if (h*opt[ans-1]<sum-y)
{
h++;
}
ok=h;
}
}
ll a1=query(ver[u],1,opt.size(),ans+1,opt.size());
ll a2=query(ver[v],1,opt.size(),ans+1,opt.size());
ll a3=query(ver[parent],1,opt.size(),ans+1,opt.size());
ok+=a1+a2-2*a3;
if (ok<=x)
{
cout<<x-ok<<nl;
}
else cout<<-1<<nl;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);}
int t;
t=1;
//cin>>t;
while (t--){optmushnpr();}
}
// goodbye see ya
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:286:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
286 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:287:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
287 | freopen(task".out","w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5040 KB |
Output is correct |
4 |
Correct |
4 ms |
5076 KB |
Output is correct |
5 |
Correct |
11 ms |
6228 KB |
Output is correct |
6 |
Correct |
13 ms |
6256 KB |
Output is correct |
7 |
Correct |
11 ms |
5932 KB |
Output is correct |
8 |
Correct |
12 ms |
6332 KB |
Output is correct |
9 |
Correct |
12 ms |
6228 KB |
Output is correct |
10 |
Correct |
12 ms |
6228 KB |
Output is correct |
11 |
Correct |
12 ms |
6284 KB |
Output is correct |
12 |
Correct |
12 ms |
6324 KB |
Output is correct |
13 |
Correct |
16 ms |
6468 KB |
Output is correct |
14 |
Correct |
18 ms |
6356 KB |
Output is correct |
15 |
Correct |
13 ms |
6356 KB |
Output is correct |
16 |
Correct |
12 ms |
6336 KB |
Output is correct |
17 |
Correct |
13 ms |
6336 KB |
Output is correct |
18 |
Correct |
12 ms |
6320 KB |
Output is correct |
19 |
Correct |
11 ms |
6340 KB |
Output is correct |
20 |
Correct |
12 ms |
6332 KB |
Output is correct |
21 |
Correct |
11 ms |
6228 KB |
Output is correct |
22 |
Correct |
14 ms |
6228 KB |
Output is correct |
23 |
Correct |
13 ms |
6284 KB |
Output is correct |
24 |
Correct |
16 ms |
6228 KB |
Output is correct |
25 |
Correct |
13 ms |
6340 KB |
Output is correct |
26 |
Correct |
12 ms |
6340 KB |
Output is correct |
27 |
Correct |
11 ms |
6340 KB |
Output is correct |
28 |
Correct |
11 ms |
6228 KB |
Output is correct |
29 |
Correct |
10 ms |
6228 KB |
Output is correct |
30 |
Correct |
7 ms |
5828 KB |
Output is correct |
31 |
Correct |
9 ms |
5716 KB |
Output is correct |
32 |
Correct |
7 ms |
5820 KB |
Output is correct |
33 |
Correct |
12 ms |
6484 KB |
Output is correct |
34 |
Correct |
12 ms |
6472 KB |
Output is correct |
35 |
Correct |
13 ms |
6484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
6 ms |
5716 KB |
Output is correct |
3 |
Correct |
6 ms |
5824 KB |
Output is correct |
4 |
Correct |
8 ms |
5828 KB |
Output is correct |
5 |
Correct |
266 ms |
41864 KB |
Output is correct |
6 |
Correct |
212 ms |
33200 KB |
Output is correct |
7 |
Correct |
214 ms |
35872 KB |
Output is correct |
8 |
Correct |
162 ms |
36036 KB |
Output is correct |
9 |
Correct |
194 ms |
36172 KB |
Output is correct |
10 |
Correct |
257 ms |
43376 KB |
Output is correct |
11 |
Correct |
308 ms |
43420 KB |
Output is correct |
12 |
Correct |
233 ms |
43324 KB |
Output is correct |
13 |
Correct |
258 ms |
43332 KB |
Output is correct |
14 |
Correct |
256 ms |
43384 KB |
Output is correct |
15 |
Correct |
300 ms |
50752 KB |
Output is correct |
16 |
Correct |
351 ms |
51200 KB |
Output is correct |
17 |
Correct |
325 ms |
50344 KB |
Output is correct |
18 |
Correct |
315 ms |
43412 KB |
Output is correct |
19 |
Correct |
320 ms |
43220 KB |
Output is correct |
20 |
Correct |
310 ms |
43484 KB |
Output is correct |
21 |
Correct |
208 ms |
42744 KB |
Output is correct |
22 |
Correct |
257 ms |
42984 KB |
Output is correct |
23 |
Correct |
220 ms |
42984 KB |
Output is correct |
24 |
Correct |
177 ms |
43008 KB |
Output is correct |
25 |
Correct |
264 ms |
43252 KB |
Output is correct |
26 |
Correct |
227 ms |
43172 KB |
Output is correct |
27 |
Correct |
227 ms |
43216 KB |
Output is correct |
28 |
Correct |
198 ms |
43116 KB |
Output is correct |
29 |
Correct |
192 ms |
43160 KB |
Output is correct |
30 |
Correct |
196 ms |
43392 KB |
Output is correct |
31 |
Correct |
227 ms |
43396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4948 KB |
Output is correct |
2 |
Correct |
12 ms |
6476 KB |
Output is correct |
3 |
Correct |
13 ms |
6404 KB |
Output is correct |
4 |
Correct |
16 ms |
6484 KB |
Output is correct |
5 |
Correct |
814 ms |
70420 KB |
Output is correct |
6 |
Correct |
798 ms |
63068 KB |
Output is correct |
7 |
Correct |
1273 ms |
70620 KB |
Output is correct |
8 |
Correct |
1769 ms |
90448 KB |
Output is correct |
9 |
Correct |
1602 ms |
90428 KB |
Output is correct |
10 |
Correct |
1807 ms |
90456 KB |
Output is correct |
11 |
Correct |
1381 ms |
90000 KB |
Output is correct |
12 |
Correct |
1427 ms |
90080 KB |
Output is correct |
13 |
Correct |
1687 ms |
90184 KB |
Output is correct |
14 |
Correct |
918 ms |
90392 KB |
Output is correct |
15 |
Correct |
1032 ms |
90328 KB |
Output is correct |
16 |
Correct |
1093 ms |
90596 KB |
Output is correct |
17 |
Correct |
1075 ms |
90488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Correct |
4 ms |
5040 KB |
Output is correct |
4 |
Correct |
4 ms |
5076 KB |
Output is correct |
5 |
Correct |
11 ms |
6228 KB |
Output is correct |
6 |
Correct |
13 ms |
6256 KB |
Output is correct |
7 |
Correct |
11 ms |
5932 KB |
Output is correct |
8 |
Correct |
12 ms |
6332 KB |
Output is correct |
9 |
Correct |
12 ms |
6228 KB |
Output is correct |
10 |
Correct |
12 ms |
6228 KB |
Output is correct |
11 |
Correct |
12 ms |
6284 KB |
Output is correct |
12 |
Correct |
12 ms |
6324 KB |
Output is correct |
13 |
Correct |
16 ms |
6468 KB |
Output is correct |
14 |
Correct |
18 ms |
6356 KB |
Output is correct |
15 |
Correct |
13 ms |
6356 KB |
Output is correct |
16 |
Correct |
12 ms |
6336 KB |
Output is correct |
17 |
Correct |
13 ms |
6336 KB |
Output is correct |
18 |
Correct |
12 ms |
6320 KB |
Output is correct |
19 |
Correct |
11 ms |
6340 KB |
Output is correct |
20 |
Correct |
12 ms |
6332 KB |
Output is correct |
21 |
Correct |
11 ms |
6228 KB |
Output is correct |
22 |
Correct |
14 ms |
6228 KB |
Output is correct |
23 |
Correct |
13 ms |
6284 KB |
Output is correct |
24 |
Correct |
16 ms |
6228 KB |
Output is correct |
25 |
Correct |
13 ms |
6340 KB |
Output is correct |
26 |
Correct |
12 ms |
6340 KB |
Output is correct |
27 |
Correct |
11 ms |
6340 KB |
Output is correct |
28 |
Correct |
11 ms |
6228 KB |
Output is correct |
29 |
Correct |
10 ms |
6228 KB |
Output is correct |
30 |
Correct |
7 ms |
5828 KB |
Output is correct |
31 |
Correct |
9 ms |
5716 KB |
Output is correct |
32 |
Correct |
7 ms |
5820 KB |
Output is correct |
33 |
Correct |
12 ms |
6484 KB |
Output is correct |
34 |
Correct |
12 ms |
6472 KB |
Output is correct |
35 |
Correct |
13 ms |
6484 KB |
Output is correct |
36 |
Correct |
3 ms |
4948 KB |
Output is correct |
37 |
Correct |
6 ms |
5716 KB |
Output is correct |
38 |
Correct |
6 ms |
5824 KB |
Output is correct |
39 |
Correct |
8 ms |
5828 KB |
Output is correct |
40 |
Correct |
266 ms |
41864 KB |
Output is correct |
41 |
Correct |
212 ms |
33200 KB |
Output is correct |
42 |
Correct |
214 ms |
35872 KB |
Output is correct |
43 |
Correct |
162 ms |
36036 KB |
Output is correct |
44 |
Correct |
194 ms |
36172 KB |
Output is correct |
45 |
Correct |
257 ms |
43376 KB |
Output is correct |
46 |
Correct |
308 ms |
43420 KB |
Output is correct |
47 |
Correct |
233 ms |
43324 KB |
Output is correct |
48 |
Correct |
258 ms |
43332 KB |
Output is correct |
49 |
Correct |
256 ms |
43384 KB |
Output is correct |
50 |
Correct |
300 ms |
50752 KB |
Output is correct |
51 |
Correct |
351 ms |
51200 KB |
Output is correct |
52 |
Correct |
325 ms |
50344 KB |
Output is correct |
53 |
Correct |
315 ms |
43412 KB |
Output is correct |
54 |
Correct |
320 ms |
43220 KB |
Output is correct |
55 |
Correct |
310 ms |
43484 KB |
Output is correct |
56 |
Correct |
208 ms |
42744 KB |
Output is correct |
57 |
Correct |
257 ms |
42984 KB |
Output is correct |
58 |
Correct |
220 ms |
42984 KB |
Output is correct |
59 |
Correct |
177 ms |
43008 KB |
Output is correct |
60 |
Correct |
264 ms |
43252 KB |
Output is correct |
61 |
Correct |
227 ms |
43172 KB |
Output is correct |
62 |
Correct |
227 ms |
43216 KB |
Output is correct |
63 |
Correct |
198 ms |
43116 KB |
Output is correct |
64 |
Correct |
192 ms |
43160 KB |
Output is correct |
65 |
Correct |
196 ms |
43392 KB |
Output is correct |
66 |
Correct |
227 ms |
43396 KB |
Output is correct |
67 |
Correct |
4 ms |
4948 KB |
Output is correct |
68 |
Correct |
12 ms |
6476 KB |
Output is correct |
69 |
Correct |
13 ms |
6404 KB |
Output is correct |
70 |
Correct |
16 ms |
6484 KB |
Output is correct |
71 |
Correct |
814 ms |
70420 KB |
Output is correct |
72 |
Correct |
798 ms |
63068 KB |
Output is correct |
73 |
Correct |
1273 ms |
70620 KB |
Output is correct |
74 |
Correct |
1769 ms |
90448 KB |
Output is correct |
75 |
Correct |
1602 ms |
90428 KB |
Output is correct |
76 |
Correct |
1807 ms |
90456 KB |
Output is correct |
77 |
Correct |
1381 ms |
90000 KB |
Output is correct |
78 |
Correct |
1427 ms |
90080 KB |
Output is correct |
79 |
Correct |
1687 ms |
90184 KB |
Output is correct |
80 |
Correct |
918 ms |
90392 KB |
Output is correct |
81 |
Correct |
1032 ms |
90328 KB |
Output is correct |
82 |
Correct |
1093 ms |
90596 KB |
Output is correct |
83 |
Correct |
1075 ms |
90488 KB |
Output is correct |
84 |
Correct |
576 ms |
74064 KB |
Output is correct |
85 |
Correct |
636 ms |
61720 KB |
Output is correct |
86 |
Correct |
588 ms |
48832 KB |
Output is correct |
87 |
Correct |
913 ms |
82496 KB |
Output is correct |
88 |
Correct |
942 ms |
82520 KB |
Output is correct |
89 |
Correct |
958 ms |
82472 KB |
Output is correct |
90 |
Correct |
999 ms |
82620 KB |
Output is correct |
91 |
Correct |
907 ms |
82532 KB |
Output is correct |
92 |
Correct |
1683 ms |
87516 KB |
Output is correct |
93 |
Correct |
1590 ms |
89140 KB |
Output is correct |
94 |
Correct |
1240 ms |
82616 KB |
Output is correct |
95 |
Correct |
1239 ms |
82588 KB |
Output is correct |
96 |
Correct |
1141 ms |
82672 KB |
Output is correct |
97 |
Correct |
1244 ms |
82488 KB |
Output is correct |
98 |
Correct |
815 ms |
82144 KB |
Output is correct |
99 |
Correct |
828 ms |
82000 KB |
Output is correct |
100 |
Correct |
795 ms |
82132 KB |
Output is correct |
101 |
Correct |
809 ms |
82224 KB |
Output is correct |
102 |
Correct |
965 ms |
82580 KB |
Output is correct |
103 |
Correct |
941 ms |
82412 KB |
Output is correct |
104 |
Correct |
951 ms |
82356 KB |
Output is correct |
105 |
Correct |
776 ms |
82532 KB |
Output is correct |
106 |
Correct |
803 ms |
82496 KB |
Output is correct |
107 |
Correct |
830 ms |
82452 KB |
Output is correct |
108 |
Correct |
782 ms |
82348 KB |
Output is correct |