#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
struct segtree{
using T = array<int, 2>;
vector<T> st;
vector<int> ar;
int n, tl, tr;
T base = {0, 0};
segtree(){
st.resize(1);
};
T merge(T x, T y){
x[0] += y[0]; x[1] += y[1];
return x;
}
segtree(vector<int> a){
ar = a;
n = a.size();
st.resize(n*4, base);
build(1, 0, n-1);
}
void build(int v, int l, int r){
if(l==r){
st[v] = {0, ar[l]};
}
else if(l < r){
int mid = (l + r) / 2;
build(v*2, l, mid);
build(v*2+1, mid+1, r);
st[v] = merge(st[v*2], st[v*2+1]);
}
}
void upd(int v, int l, int r, int pos, T x){
if(l==r){
st[v] = merge(st[v], x);
}
else if(l<r){
int mid = (l+r) / 2;
if (pos <= mid)upd(v*2, l, mid, pos, x);
else upd(v*2+1, mid+1, r, pos, x);
st[v] = merge(st[v*2], st[v*2+1]);
}
}
void upd(int v, T gh){
upd(1, 0, n-1, v, gh);
}
T get(int v, int l, int r){
if(r<tl || l > tr) return base;
else if(l>=tl && r<= tr){
return st[v];
}
else{
int mid = (l+r) / 2;
return merge(get(v*2, l, mid), get(v*2+1, mid+1, r));
}
}
T operator()(int l, int r){
tl = l; tr = r;
if(l>r) return {0, 0};
return get(1, 0, n-1);
}
};
vector<segtree> st;
struct hld{
vector<vector<array<int, 2>>> g;
vector<vector<int>> chain;
vector<int> s, c, d, p_node, p_edge, val;
vector<int> pos_edge, ind_edge;
vector<int> pos_node, ind_node;
int n;
hld(){};
hld(int _n, vector<vector<array<int, 2>>>a, vector<int> v){
n = _n; g = a;
s.resize(n, 1); d.resize(n);
pos_edge.resize(n); ind_edge.resize(n);
pos_node.resize(n); ind_node.resize(n);
p_edge.resize(n);
p_node.resize(n);
val = v;
d[0] = -1;
dfs(0, 0); dfs2(0, 0);
p_edge[0] = n-1;
for(int i=0; i<chain.size(); i++){
reverse(chain[i].begin(), chain[i].end());
vector<int> x;
for(int l=0; l<chain[i].size(); l++){
int node = chain[i][l];
int edge = p_edge[node];
ind_edge[edge] = ind_node[node] = l;
pos_edge[edge] = pos_node[node] = i;
x.push_back(val[edge]);
}
st.push_back(segtree(x));
}
};
void dfs(int v, int par){
p_node[v] = par;
for(int i = 0; i <g[v].size(); i++){
auto [x, y] = g[v][i];
if(x!=par){
dfs(x, v);
p_edge[x] = y;
s[v] += s[x];
if(s[x] > s[g[v][0][0]]||g[v][0][0]==par){
swap(g[v][0], g[v][i]);
}
}
}
}
void dfs2(int v, int p){
c.push_back(v);
d[v] = d[p]+1;
for(auto &[x, y]: g[v]){
if(x==p) continue;
dfs2(x, v);
}
if(g[v].size()==1 && v!=p && c.size()){
chain.push_back(c);
c.clear();
}
}
array<int, 2> merge(array<int, 2> x, array<int, 2> y){
x[0] += y[0]; x[1] += y[1];
return x;
}
array<int, 2> get(int v, int u){
int pv = pos_node[v], pu = pos_node[u];
array<int, 2> gh ={0, 0};
while(pv != pu){
if(d[chain[pu].back()] > d[chain[pv].back()]){
swap(pv, pu);
swap(u, v);
}
gh=merge(gh, st[pv](ind_node[v], ind_node[chain[pv].back()]));
v = p_node[chain[pv].back()];
pv = pos_node[v];
}
if(d[v] <d[u]) swap(u, v);
gh = merge(gh, st[pv](ind_node[v], ind_node[u]-1));
return gh;
}
};
hld h;
struct comparer{
int k = 0;
int n;
vector<array<int, 2>> val;
vector<int> ind;
comparer(vector<array<int, 2>> v){
n = v.size();
val = v;
k = 0;
ind.resize(n);
iota(ind.begin(), ind.end(), 0);
sort(ind.begin(), ind.end(), [&](int x, int y){
return val[x][1] > val[y][1];
});
};
void operator++(){
int pf = val[ind[k]][0];
int pos= h.pos_edge[pf];
int id = h.ind_edge[pf];
auto x = st[pos](id, id);
st[pos].upd(id, {1, -val[ind[k]][1]});
x = st[pos](id, id);
k++;
}
void operator--(){
k--;
int pf = val[ind[k]][0];
int pos= h.pos_edge[pf];
int id = h.ind_edge[pf];
st[pos].upd(id, {-1, val[ind[k]][1]});
}
};
struct query{
int u=0, v=0;
int x=0, y=0;
int ind=0;
query(){};
query(array<int, 5> s){
u=s[0]; v = s[1]; x=s[2]; y=s[3];
ind = s[4];
}
bool check(){
auto a = h.get(u, v);
return (a[0]<x && a[1]>y);
}
int check2(){
auto a = h.get(u, v);
if(a[0]<=x && a[1]<=y){
return x-a[0];
}
return -1;
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, q; cin >> n >> m >> q;
n++;
vector<int> val(n);
vector<array<int, 2>> val2(m);
vector<vector<array<int, 2>>> g(n);
vector<array<int, 2>> e(n-2);
for (auto &[x, y]: e){
cin >> x >> y;
x--; y--;
}
e.push_back({0, n-1});
for(int i=0; i<m; i++){
int z, c; cin >> z >> c;
val[z-1] += c;
val2[i]={z-1, c};
}
for(int i=0; i<n; i++){
if(val[i]==0) val2.push_back({i, 0});
}
for(int i=0; i<n-1; i++){
auto [x, y]=e[i];
g[x].push_back({y, i});
g[y].push_back({x, i});
}
h = hld(n, g, val);
comparer cmp(val2);
vector<query> qu(q);
for(int i=0; i<q; i++){
array<int, 5> f;
for(int l=0; l<4; l++) cin >> f[l];
f[0]--; f[1]--;
f[4] = i;
qu[i] = query(f);
}
vector<int> ans(q);
auto rec = [&](vector<query> x, int l, int r,auto &&rec)->void{
// cout<<l<<" "<<r<<"\n";
if(l==r){
while(cmp.k<l){
++cmp;
}
while(cmp.k>l){
--cmp;
}
for(auto i: x){
// cout<<i.ind<<" "<<cmp.k<<"a\n";
ans[i.ind] = i.check2();
}
}
else if(l<r){
vector<query> a, b;
int mid = (l+r)/2;
while(cmp.k < mid){
++cmp;
}
while(cmp.k > mid){
--cmp;
}
//cout<<l<<" "<<r<<"\n";
for(auto i: x){
if(i.check()) a.push_back(i);
else b.push_back(i);
}
if(a.size())
rec(a, mid+1, r, rec);
if(b.size())
rec(b, l, mid, rec);
}
};
rec(qu, 0, val2.size()-1, rec);
for(auto i: ans) cout<<i<<"\n";
}
Compilation message
currencies.cpp: In constructor 'hld::hld(long long int, std::vector<std::vector<std::array<long long int, 2> > >, std::vector<long long int>)':
currencies.cpp:111:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i=0; i<chain.size(); i++){
| ~^~~~~~~~~~~~~
currencies.cpp:115:27: 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]
115 | for(int l=0; l<chain[i].size(); l++){
| ~^~~~~~~~~~~~~~~~
currencies.cpp: In member function 'void hld::dfs(long long int, long long int)':
currencies.cpp:133:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(int i = 0; i <g[v].size(); i++){
| ~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
456 KB |
Output is correct |
5 |
Correct |
6 ms |
1884 KB |
Output is correct |
6 |
Correct |
8 ms |
2652 KB |
Output is correct |
7 |
Correct |
7 ms |
2140 KB |
Output is correct |
8 |
Correct |
8 ms |
2136 KB |
Output is correct |
9 |
Correct |
9 ms |
2140 KB |
Output is correct |
10 |
Correct |
10 ms |
2136 KB |
Output is correct |
11 |
Correct |
9 ms |
2136 KB |
Output is correct |
12 |
Correct |
8 ms |
2140 KB |
Output is correct |
13 |
Correct |
10 ms |
1800 KB |
Output is correct |
14 |
Correct |
10 ms |
1936 KB |
Output is correct |
15 |
Correct |
11 ms |
1780 KB |
Output is correct |
16 |
Correct |
10 ms |
1956 KB |
Output is correct |
17 |
Correct |
10 ms |
1884 KB |
Output is correct |
18 |
Correct |
11 ms |
1904 KB |
Output is correct |
19 |
Correct |
6 ms |
2752 KB |
Output is correct |
20 |
Correct |
5 ms |
2908 KB |
Output is correct |
21 |
Correct |
5 ms |
2904 KB |
Output is correct |
22 |
Correct |
5 ms |
2680 KB |
Output is correct |
23 |
Correct |
10 ms |
2140 KB |
Output is correct |
24 |
Correct |
8 ms |
2136 KB |
Output is correct |
25 |
Correct |
8 ms |
2396 KB |
Output is correct |
26 |
Correct |
7 ms |
2120 KB |
Output is correct |
27 |
Correct |
6 ms |
2396 KB |
Output is correct |
28 |
Correct |
6 ms |
2104 KB |
Output is correct |
29 |
Correct |
7 ms |
3672 KB |
Output is correct |
30 |
Correct |
8 ms |
2140 KB |
Output is correct |
31 |
Correct |
8 ms |
2008 KB |
Output is correct |
32 |
Correct |
11 ms |
2104 KB |
Output is correct |
33 |
Correct |
10 ms |
1880 KB |
Output is correct |
34 |
Correct |
10 ms |
1884 KB |
Output is correct |
35 |
Correct |
10 ms |
1872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
8 ms |
2140 KB |
Output is correct |
3 |
Correct |
10 ms |
2140 KB |
Output is correct |
4 |
Correct |
10 ms |
2140 KB |
Output is correct |
5 |
Correct |
1150 ms |
98052 KB |
Output is correct |
6 |
Correct |
1256 ms |
112932 KB |
Output is correct |
7 |
Correct |
1326 ms |
119024 KB |
Output is correct |
8 |
Correct |
938 ms |
98792 KB |
Output is correct |
9 |
Correct |
1020 ms |
91636 KB |
Output is correct |
10 |
Correct |
1730 ms |
92268 KB |
Output is correct |
11 |
Correct |
1444 ms |
87556 KB |
Output is correct |
12 |
Correct |
1602 ms |
89164 KB |
Output is correct |
13 |
Correct |
1868 ms |
88880 KB |
Output is correct |
14 |
Correct |
1534 ms |
86272 KB |
Output is correct |
15 |
Correct |
1084 ms |
80036 KB |
Output is correct |
16 |
Correct |
1156 ms |
82036 KB |
Output is correct |
17 |
Correct |
1223 ms |
78032 KB |
Output is correct |
18 |
Correct |
1535 ms |
73764 KB |
Output is correct |
19 |
Correct |
1605 ms |
72376 KB |
Output is correct |
20 |
Correct |
1529 ms |
74052 KB |
Output is correct |
21 |
Correct |
1014 ms |
147888 KB |
Output is correct |
22 |
Correct |
837 ms |
147556 KB |
Output is correct |
23 |
Correct |
780 ms |
147448 KB |
Output is correct |
24 |
Correct |
718 ms |
149364 KB |
Output is correct |
25 |
Correct |
1098 ms |
94564 KB |
Output is correct |
26 |
Correct |
1336 ms |
90436 KB |
Output is correct |
27 |
Correct |
1263 ms |
93432 KB |
Output is correct |
28 |
Correct |
518 ms |
95260 KB |
Output is correct |
29 |
Correct |
449 ms |
109380 KB |
Output is correct |
30 |
Correct |
794 ms |
90264 KB |
Output is correct |
31 |
Correct |
653 ms |
91188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
10 ms |
2240 KB |
Output is correct |
3 |
Correct |
10 ms |
1884 KB |
Output is correct |
4 |
Correct |
10 ms |
1884 KB |
Output is correct |
5 |
Correct |
671 ms |
91600 KB |
Output is correct |
6 |
Correct |
766 ms |
96816 KB |
Output is correct |
7 |
Correct |
875 ms |
92896 KB |
Output is correct |
8 |
Correct |
1141 ms |
78548 KB |
Output is correct |
9 |
Correct |
1210 ms |
78788 KB |
Output is correct |
10 |
Correct |
1262 ms |
79848 KB |
Output is correct |
11 |
Correct |
846 ms |
81832 KB |
Output is correct |
12 |
Correct |
864 ms |
80184 KB |
Output is correct |
13 |
Correct |
847 ms |
81548 KB |
Output is correct |
14 |
Correct |
728 ms |
80616 KB |
Output is correct |
15 |
Correct |
601 ms |
79088 KB |
Output is correct |
16 |
Correct |
726 ms |
79340 KB |
Output is correct |
17 |
Correct |
723 ms |
81260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
456 KB |
Output is correct |
5 |
Correct |
6 ms |
1884 KB |
Output is correct |
6 |
Correct |
8 ms |
2652 KB |
Output is correct |
7 |
Correct |
7 ms |
2140 KB |
Output is correct |
8 |
Correct |
8 ms |
2136 KB |
Output is correct |
9 |
Correct |
9 ms |
2140 KB |
Output is correct |
10 |
Correct |
10 ms |
2136 KB |
Output is correct |
11 |
Correct |
9 ms |
2136 KB |
Output is correct |
12 |
Correct |
8 ms |
2140 KB |
Output is correct |
13 |
Correct |
10 ms |
1800 KB |
Output is correct |
14 |
Correct |
10 ms |
1936 KB |
Output is correct |
15 |
Correct |
11 ms |
1780 KB |
Output is correct |
16 |
Correct |
10 ms |
1956 KB |
Output is correct |
17 |
Correct |
10 ms |
1884 KB |
Output is correct |
18 |
Correct |
11 ms |
1904 KB |
Output is correct |
19 |
Correct |
6 ms |
2752 KB |
Output is correct |
20 |
Correct |
5 ms |
2908 KB |
Output is correct |
21 |
Correct |
5 ms |
2904 KB |
Output is correct |
22 |
Correct |
5 ms |
2680 KB |
Output is correct |
23 |
Correct |
10 ms |
2140 KB |
Output is correct |
24 |
Correct |
8 ms |
2136 KB |
Output is correct |
25 |
Correct |
8 ms |
2396 KB |
Output is correct |
26 |
Correct |
7 ms |
2120 KB |
Output is correct |
27 |
Correct |
6 ms |
2396 KB |
Output is correct |
28 |
Correct |
6 ms |
2104 KB |
Output is correct |
29 |
Correct |
7 ms |
3672 KB |
Output is correct |
30 |
Correct |
8 ms |
2140 KB |
Output is correct |
31 |
Correct |
8 ms |
2008 KB |
Output is correct |
32 |
Correct |
11 ms |
2104 KB |
Output is correct |
33 |
Correct |
10 ms |
1880 KB |
Output is correct |
34 |
Correct |
10 ms |
1884 KB |
Output is correct |
35 |
Correct |
10 ms |
1872 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
8 ms |
2140 KB |
Output is correct |
38 |
Correct |
10 ms |
2140 KB |
Output is correct |
39 |
Correct |
10 ms |
2140 KB |
Output is correct |
40 |
Correct |
1150 ms |
98052 KB |
Output is correct |
41 |
Correct |
1256 ms |
112932 KB |
Output is correct |
42 |
Correct |
1326 ms |
119024 KB |
Output is correct |
43 |
Correct |
938 ms |
98792 KB |
Output is correct |
44 |
Correct |
1020 ms |
91636 KB |
Output is correct |
45 |
Correct |
1730 ms |
92268 KB |
Output is correct |
46 |
Correct |
1444 ms |
87556 KB |
Output is correct |
47 |
Correct |
1602 ms |
89164 KB |
Output is correct |
48 |
Correct |
1868 ms |
88880 KB |
Output is correct |
49 |
Correct |
1534 ms |
86272 KB |
Output is correct |
50 |
Correct |
1084 ms |
80036 KB |
Output is correct |
51 |
Correct |
1156 ms |
82036 KB |
Output is correct |
52 |
Correct |
1223 ms |
78032 KB |
Output is correct |
53 |
Correct |
1535 ms |
73764 KB |
Output is correct |
54 |
Correct |
1605 ms |
72376 KB |
Output is correct |
55 |
Correct |
1529 ms |
74052 KB |
Output is correct |
56 |
Correct |
1014 ms |
147888 KB |
Output is correct |
57 |
Correct |
837 ms |
147556 KB |
Output is correct |
58 |
Correct |
780 ms |
147448 KB |
Output is correct |
59 |
Correct |
718 ms |
149364 KB |
Output is correct |
60 |
Correct |
1098 ms |
94564 KB |
Output is correct |
61 |
Correct |
1336 ms |
90436 KB |
Output is correct |
62 |
Correct |
1263 ms |
93432 KB |
Output is correct |
63 |
Correct |
518 ms |
95260 KB |
Output is correct |
64 |
Correct |
449 ms |
109380 KB |
Output is correct |
65 |
Correct |
794 ms |
90264 KB |
Output is correct |
66 |
Correct |
653 ms |
91188 KB |
Output is correct |
67 |
Correct |
1 ms |
344 KB |
Output is correct |
68 |
Correct |
10 ms |
2240 KB |
Output is correct |
69 |
Correct |
10 ms |
1884 KB |
Output is correct |
70 |
Correct |
10 ms |
1884 KB |
Output is correct |
71 |
Correct |
671 ms |
91600 KB |
Output is correct |
72 |
Correct |
766 ms |
96816 KB |
Output is correct |
73 |
Correct |
875 ms |
92896 KB |
Output is correct |
74 |
Correct |
1141 ms |
78548 KB |
Output is correct |
75 |
Correct |
1210 ms |
78788 KB |
Output is correct |
76 |
Correct |
1262 ms |
79848 KB |
Output is correct |
77 |
Correct |
846 ms |
81832 KB |
Output is correct |
78 |
Correct |
864 ms |
80184 KB |
Output is correct |
79 |
Correct |
847 ms |
81548 KB |
Output is correct |
80 |
Correct |
728 ms |
80616 KB |
Output is correct |
81 |
Correct |
601 ms |
79088 KB |
Output is correct |
82 |
Correct |
726 ms |
79340 KB |
Output is correct |
83 |
Correct |
723 ms |
81260 KB |
Output is correct |
84 |
Correct |
1047 ms |
94516 KB |
Output is correct |
85 |
Correct |
820 ms |
83872 KB |
Output is correct |
86 |
Correct |
784 ms |
88368 KB |
Output is correct |
87 |
Correct |
1428 ms |
89820 KB |
Output is correct |
88 |
Correct |
1596 ms |
89300 KB |
Output is correct |
89 |
Correct |
1565 ms |
88732 KB |
Output is correct |
90 |
Correct |
1348 ms |
89104 KB |
Output is correct |
91 |
Correct |
1545 ms |
88440 KB |
Output is correct |
92 |
Correct |
1098 ms |
77288 KB |
Output is correct |
93 |
Correct |
1171 ms |
77188 KB |
Output is correct |
94 |
Correct |
1499 ms |
73624 KB |
Output is correct |
95 |
Correct |
1426 ms |
74072 KB |
Output is correct |
96 |
Correct |
1432 ms |
72740 KB |
Output is correct |
97 |
Correct |
1460 ms |
74888 KB |
Output is correct |
98 |
Correct |
918 ms |
149692 KB |
Output is correct |
99 |
Correct |
786 ms |
149292 KB |
Output is correct |
100 |
Correct |
898 ms |
147172 KB |
Output is correct |
101 |
Correct |
864 ms |
149724 KB |
Output is correct |
102 |
Correct |
1246 ms |
91408 KB |
Output is correct |
103 |
Correct |
1196 ms |
94152 KB |
Output is correct |
104 |
Correct |
1230 ms |
97412 KB |
Output is correct |
105 |
Correct |
455 ms |
95980 KB |
Output is correct |
106 |
Correct |
559 ms |
96828 KB |
Output is correct |
107 |
Correct |
638 ms |
102432 KB |
Output is correct |
108 |
Correct |
672 ms |
91100 KB |
Output is correct |