// 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 |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
5076 KB |
Output is correct |
5 |
Correct |
7 ms |
6228 KB |
Output is correct |
6 |
Correct |
8 ms |
6208 KB |
Output is correct |
7 |
Correct |
7 ms |
5940 KB |
Output is correct |
8 |
Correct |
9 ms |
6220 KB |
Output is correct |
9 |
Correct |
9 ms |
6228 KB |
Output is correct |
10 |
Correct |
9 ms |
6332 KB |
Output is correct |
11 |
Correct |
9 ms |
6336 KB |
Output is correct |
12 |
Correct |
9 ms |
6228 KB |
Output is correct |
13 |
Correct |
10 ms |
6356 KB |
Output is correct |
14 |
Correct |
10 ms |
6356 KB |
Output is correct |
15 |
Correct |
10 ms |
6360 KB |
Output is correct |
16 |
Correct |
11 ms |
6336 KB |
Output is correct |
17 |
Correct |
15 ms |
6360 KB |
Output is correct |
18 |
Correct |
10 ms |
6360 KB |
Output is correct |
19 |
Correct |
9 ms |
6332 KB |
Output is correct |
20 |
Correct |
8 ms |
6332 KB |
Output is correct |
21 |
Correct |
9 ms |
6336 KB |
Output is correct |
22 |
Correct |
9 ms |
6228 KB |
Output is correct |
23 |
Correct |
9 ms |
6228 KB |
Output is correct |
24 |
Correct |
12 ms |
6228 KB |
Output is correct |
25 |
Correct |
9 ms |
6228 KB |
Output is correct |
26 |
Correct |
8 ms |
6340 KB |
Output is correct |
27 |
Correct |
8 ms |
6336 KB |
Output is correct |
28 |
Correct |
9 ms |
6228 KB |
Output is correct |
29 |
Correct |
8 ms |
6240 KB |
Output is correct |
30 |
Correct |
5 ms |
5716 KB |
Output is correct |
31 |
Correct |
5 ms |
5716 KB |
Output is correct |
32 |
Correct |
9 ms |
5716 KB |
Output is correct |
33 |
Correct |
10 ms |
6468 KB |
Output is correct |
34 |
Correct |
11 ms |
6612 KB |
Output is correct |
35 |
Correct |
9 ms |
6484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
5 ms |
5716 KB |
Output is correct |
3 |
Correct |
5 ms |
5816 KB |
Output is correct |
4 |
Correct |
5 ms |
5716 KB |
Output is correct |
5 |
Correct |
147 ms |
41872 KB |
Output is correct |
6 |
Correct |
148 ms |
33088 KB |
Output is correct |
7 |
Correct |
152 ms |
35908 KB |
Output is correct |
8 |
Correct |
132 ms |
36060 KB |
Output is correct |
9 |
Correct |
134 ms |
36264 KB |
Output is correct |
10 |
Correct |
178 ms |
43280 KB |
Output is correct |
11 |
Correct |
182 ms |
43444 KB |
Output is correct |
12 |
Correct |
183 ms |
43328 KB |
Output is correct |
13 |
Correct |
191 ms |
43264 KB |
Output is correct |
14 |
Correct |
176 ms |
43284 KB |
Output is correct |
15 |
Correct |
253 ms |
50660 KB |
Output is correct |
16 |
Correct |
256 ms |
51184 KB |
Output is correct |
17 |
Correct |
248 ms |
50320 KB |
Output is correct |
18 |
Correct |
219 ms |
43320 KB |
Output is correct |
19 |
Correct |
254 ms |
43220 KB |
Output is correct |
20 |
Correct |
214 ms |
43336 KB |
Output is correct |
21 |
Correct |
162 ms |
42716 KB |
Output is correct |
22 |
Correct |
154 ms |
42992 KB |
Output is correct |
23 |
Correct |
148 ms |
42952 KB |
Output is correct |
24 |
Correct |
160 ms |
42924 KB |
Output is correct |
25 |
Correct |
171 ms |
43192 KB |
Output is correct |
26 |
Correct |
165 ms |
43172 KB |
Output is correct |
27 |
Correct |
176 ms |
43188 KB |
Output is correct |
28 |
Correct |
144 ms |
43060 KB |
Output is correct |
29 |
Correct |
149 ms |
43172 KB |
Output is correct |
30 |
Correct |
155 ms |
43320 KB |
Output is correct |
31 |
Correct |
152 ms |
43364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5044 KB |
Output is correct |
2 |
Correct |
12 ms |
6468 KB |
Output is correct |
3 |
Correct |
10 ms |
6484 KB |
Output is correct |
4 |
Correct |
10 ms |
6496 KB |
Output is correct |
5 |
Correct |
646 ms |
70420 KB |
Output is correct |
6 |
Correct |
592 ms |
63016 KB |
Output is correct |
7 |
Correct |
973 ms |
70748 KB |
Output is correct |
8 |
Correct |
1416 ms |
90544 KB |
Output is correct |
9 |
Correct |
1362 ms |
90444 KB |
Output is correct |
10 |
Correct |
1386 ms |
90484 KB |
Output is correct |
11 |
Correct |
1091 ms |
89992 KB |
Output is correct |
12 |
Correct |
1193 ms |
90216 KB |
Output is correct |
13 |
Correct |
1089 ms |
89960 KB |
Output is correct |
14 |
Correct |
690 ms |
90460 KB |
Output is correct |
15 |
Correct |
757 ms |
90460 KB |
Output is correct |
16 |
Correct |
880 ms |
90456 KB |
Output is correct |
17 |
Correct |
857 ms |
90464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
5076 KB |
Output is correct |
5 |
Correct |
7 ms |
6228 KB |
Output is correct |
6 |
Correct |
8 ms |
6208 KB |
Output is correct |
7 |
Correct |
7 ms |
5940 KB |
Output is correct |
8 |
Correct |
9 ms |
6220 KB |
Output is correct |
9 |
Correct |
9 ms |
6228 KB |
Output is correct |
10 |
Correct |
9 ms |
6332 KB |
Output is correct |
11 |
Correct |
9 ms |
6336 KB |
Output is correct |
12 |
Correct |
9 ms |
6228 KB |
Output is correct |
13 |
Correct |
10 ms |
6356 KB |
Output is correct |
14 |
Correct |
10 ms |
6356 KB |
Output is correct |
15 |
Correct |
10 ms |
6360 KB |
Output is correct |
16 |
Correct |
11 ms |
6336 KB |
Output is correct |
17 |
Correct |
15 ms |
6360 KB |
Output is correct |
18 |
Correct |
10 ms |
6360 KB |
Output is correct |
19 |
Correct |
9 ms |
6332 KB |
Output is correct |
20 |
Correct |
8 ms |
6332 KB |
Output is correct |
21 |
Correct |
9 ms |
6336 KB |
Output is correct |
22 |
Correct |
9 ms |
6228 KB |
Output is correct |
23 |
Correct |
9 ms |
6228 KB |
Output is correct |
24 |
Correct |
12 ms |
6228 KB |
Output is correct |
25 |
Correct |
9 ms |
6228 KB |
Output is correct |
26 |
Correct |
8 ms |
6340 KB |
Output is correct |
27 |
Correct |
8 ms |
6336 KB |
Output is correct |
28 |
Correct |
9 ms |
6228 KB |
Output is correct |
29 |
Correct |
8 ms |
6240 KB |
Output is correct |
30 |
Correct |
5 ms |
5716 KB |
Output is correct |
31 |
Correct |
5 ms |
5716 KB |
Output is correct |
32 |
Correct |
9 ms |
5716 KB |
Output is correct |
33 |
Correct |
10 ms |
6468 KB |
Output is correct |
34 |
Correct |
11 ms |
6612 KB |
Output is correct |
35 |
Correct |
9 ms |
6484 KB |
Output is correct |
36 |
Correct |
3 ms |
4948 KB |
Output is correct |
37 |
Correct |
5 ms |
5716 KB |
Output is correct |
38 |
Correct |
5 ms |
5816 KB |
Output is correct |
39 |
Correct |
5 ms |
5716 KB |
Output is correct |
40 |
Correct |
147 ms |
41872 KB |
Output is correct |
41 |
Correct |
148 ms |
33088 KB |
Output is correct |
42 |
Correct |
152 ms |
35908 KB |
Output is correct |
43 |
Correct |
132 ms |
36060 KB |
Output is correct |
44 |
Correct |
134 ms |
36264 KB |
Output is correct |
45 |
Correct |
178 ms |
43280 KB |
Output is correct |
46 |
Correct |
182 ms |
43444 KB |
Output is correct |
47 |
Correct |
183 ms |
43328 KB |
Output is correct |
48 |
Correct |
191 ms |
43264 KB |
Output is correct |
49 |
Correct |
176 ms |
43284 KB |
Output is correct |
50 |
Correct |
253 ms |
50660 KB |
Output is correct |
51 |
Correct |
256 ms |
51184 KB |
Output is correct |
52 |
Correct |
248 ms |
50320 KB |
Output is correct |
53 |
Correct |
219 ms |
43320 KB |
Output is correct |
54 |
Correct |
254 ms |
43220 KB |
Output is correct |
55 |
Correct |
214 ms |
43336 KB |
Output is correct |
56 |
Correct |
162 ms |
42716 KB |
Output is correct |
57 |
Correct |
154 ms |
42992 KB |
Output is correct |
58 |
Correct |
148 ms |
42952 KB |
Output is correct |
59 |
Correct |
160 ms |
42924 KB |
Output is correct |
60 |
Correct |
171 ms |
43192 KB |
Output is correct |
61 |
Correct |
165 ms |
43172 KB |
Output is correct |
62 |
Correct |
176 ms |
43188 KB |
Output is correct |
63 |
Correct |
144 ms |
43060 KB |
Output is correct |
64 |
Correct |
149 ms |
43172 KB |
Output is correct |
65 |
Correct |
155 ms |
43320 KB |
Output is correct |
66 |
Correct |
152 ms |
43364 KB |
Output is correct |
67 |
Correct |
2 ms |
5044 KB |
Output is correct |
68 |
Correct |
12 ms |
6468 KB |
Output is correct |
69 |
Correct |
10 ms |
6484 KB |
Output is correct |
70 |
Correct |
10 ms |
6496 KB |
Output is correct |
71 |
Correct |
646 ms |
70420 KB |
Output is correct |
72 |
Correct |
592 ms |
63016 KB |
Output is correct |
73 |
Correct |
973 ms |
70748 KB |
Output is correct |
74 |
Correct |
1416 ms |
90544 KB |
Output is correct |
75 |
Correct |
1362 ms |
90444 KB |
Output is correct |
76 |
Correct |
1386 ms |
90484 KB |
Output is correct |
77 |
Correct |
1091 ms |
89992 KB |
Output is correct |
78 |
Correct |
1193 ms |
90216 KB |
Output is correct |
79 |
Correct |
1089 ms |
89960 KB |
Output is correct |
80 |
Correct |
690 ms |
90460 KB |
Output is correct |
81 |
Correct |
757 ms |
90460 KB |
Output is correct |
82 |
Correct |
880 ms |
90456 KB |
Output is correct |
83 |
Correct |
857 ms |
90464 KB |
Output is correct |
84 |
Correct |
438 ms |
73848 KB |
Output is correct |
85 |
Correct |
535 ms |
61740 KB |
Output is correct |
86 |
Correct |
504 ms |
48676 KB |
Output is correct |
87 |
Correct |
793 ms |
82368 KB |
Output is correct |
88 |
Correct |
784 ms |
82436 KB |
Output is correct |
89 |
Correct |
811 ms |
82416 KB |
Output is correct |
90 |
Correct |
812 ms |
82464 KB |
Output is correct |
91 |
Correct |
830 ms |
82368 KB |
Output is correct |
92 |
Correct |
1541 ms |
87536 KB |
Output is correct |
93 |
Correct |
1473 ms |
89344 KB |
Output is correct |
94 |
Correct |
1049 ms |
82460 KB |
Output is correct |
95 |
Correct |
1052 ms |
82492 KB |
Output is correct |
96 |
Correct |
1049 ms |
82472 KB |
Output is correct |
97 |
Correct |
1067 ms |
82476 KB |
Output is correct |
98 |
Correct |
690 ms |
82108 KB |
Output is correct |
99 |
Correct |
691 ms |
82132 KB |
Output is correct |
100 |
Correct |
692 ms |
82140 KB |
Output is correct |
101 |
Correct |
674 ms |
82272 KB |
Output is correct |
102 |
Correct |
816 ms |
82368 KB |
Output is correct |
103 |
Correct |
862 ms |
82340 KB |
Output is correct |
104 |
Correct |
793 ms |
82336 KB |
Output is correct |
105 |
Correct |
660 ms |
82664 KB |
Output is correct |
106 |
Correct |
655 ms |
82492 KB |
Output is correct |
107 |
Correct |
642 ms |
82528 KB |
Output is correct |
108 |
Correct |
632 ms |
82396 KB |
Output is correct |