// header file
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// macros
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int lim = 1e5 + 5;
struct fenwick {
ll a[lim];
fenwick() {
memset(a, 0, sizeof(a));
}
void update(int idx, int val) {
while(idx < lim) {
a[idx] += val;
idx += idx&-idx;
}
}
void update(int l, int r, int val) {
update(l, val);
update(r + 1, -val);
}
ll query(int idx) {
ll ret = 0;
while(idx) {
ret += a[idx];
idx -= idx&-idx;
}
return ret;
}
};
vector<int> edges[lim];
int par[17][lim], in[lim], out[lim], ti, depth[lim];
bool vis[lim];
void dfs(int nd) {
vis[nd] = 1;
in[nd] = ++ti;
for(int i = 1; i < 17; ++i) {
par[i][nd] = par[i - 1][par[i - 1][nd]];
}
for(auto i : edges[nd]) {
if(!vis[i]) {
depth[i] = depth[nd] + 1;
par[0][i] = nd;
dfs(i);
}
}
out[nd] = ti;
}
int lca(int u, int v) {
if(depth[u] > depth[v])
swap(u, v);
for(int i = 16; i >= 0; --i) {
if(depth[par[i][v]] >= depth[u])
v = par[i][v];
}
if(u == v)
return u;
for(int i = 16; i >= 0; --i) {
if(par[i][u] != par[i][v])
u = par[i][u], v = par[i][v];
}
return par[0][u];
}
struct query {
int l, r, m, num, s, t;
ll x, y;
bool operator<(const query& rhs) const {
return m > rhs.m;
};
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(NULL);
// dsu on tree dr min weight, nanti bisa di paralel binser berapa max yg bs didapat
// find count of "used" edges in a path
// HLD + binser -> Nlog^3N
// coba non HLD atau coba HLD tapi ga pake binsernya
// find count of "used" in path, sum edgesnya berapa?
// simpan dist i ke root dan j ke root
// nanti di update lazy seg, terus simpen LCA
// jadinya binser + mst + ett + seg/fen
// greedy edge dr yg cost terkecil ke terbesar, nanti simpan count used edges berapa (bisa pakai teknik yg sama juga)
// bisa pakai segtree biasa, difference array style
int n, m, q;
cin >> n >> m >> q;
pair<int, int> adj[n];
for(int i = 1; i <= n - 1; ++i) {
int u, v;
cin >> u >> v;
edges[u].pb(v);
edges[v].pb(u);
adj[i] = mp(u, v);
}
dfs(1);
for(auto &i : adj) {
if(depth[i.fi] < depth[i.se])
swap(i.fi, i.se);
}
// fi -> price
// se -> idx
fenwick cost, count;
pair<int, int> periksa[m];
for(int i = 0; i < m; ++i) {
cin >> periksa[i].se >> periksa[i].fi;
}
sort(periksa, periksa + m);
ll ans[q];
memset(ans, -1, sizeof(ans));
vector<query> queries[2][m + 1];
for(int i = 0; i < q; ++i) {
ll s, t, x, y;
cin >> s >> t >> x >> y;
query a;
a.x = x, a.y = y, a.l = 0, a.r = m, a.m = (a.l + a.r) >> 1, a.num = i;
a.s = s, a.t = t;
queries[1][a.m].pb(a);
}
for(int iter = 0; iter < 18; ++iter) {
// coba jalanin paralel binser
// count: jumlah emas yg digunakan
int idx = iter & 1;
for(int i = 0; i < m; ++i)
queries[idx][i].clear();
for(auto i : periksa) {
count.update(in[adj[i.se].fi], out[adj[i.se].fi], 1);
}
for(int i = 0; i < m; ++i) {
// before update di proses dulu
for(auto j : queries[idx ^ 1][i]) {
int r = lca(j.s, j.t);
ll perak = cost.query(in[j.s]) + cost.query(in[j.t]) - 2 * cost.query(in[r]);
int emas = count.query(in[j.s]) + count.query(in[j.t]) - 2 * count.query(in[r]);
//cout << j.num << endl;
//cout << "INDEX " << i << endl;
//cout << "PERAK " << perak << " " << j.y << endl;
//cout << "EMAS " << emas << " " << j.x << endl;
if(perak <= j.y && emas <= j.x) {
ans[j.num] = max(ans[j.num], j.x - emas);
}
if(perak <= j.y) {
j.l = j.m + 1;
}
else {
j.r = j.m - 1;
}
j.m = (j.l + j.r) >> 1;
queries[idx][j.m].pb(j);
}
// update cost/count
// u higher depth
int u = adj[periksa[i].se].fi, v = adj[periksa[i].se].se;
ll harga = periksa[i].fi;
count.update(in[u], out[u], -1);
cost.update(in[u], out[u], harga);
}
for(auto j : queries[idx ^ 1][m]) {
int r = lca(j.s, j.t);
ll perak = cost.query(in[j.s]) + cost.query(in[j.t]) - 2 * cost.query(in[r]);
int emas = count.query(in[j.s]) + count.query(in[j.t]) - 2 * count.query(in[r]);
//cout << j.num << endl;
//cout << "INDEX " << i << endl;
//cout << "PERAK " << perak << " " << j.y << endl;
//cout << "EMAS " << emas << " " << j.x << endl;
if(perak <= j.y && emas <= j.x) {
ans[j.num] = max(ans[j.num], j.x - emas);
}
if(perak <= j.y) {
j.l = j.m + 1;
}
else {
j.r = j.m - 1;
}
j.m = (j.l + j.r) >> 1;
queries[idx][j.m].pb(j);
}
memset(cost.a, 0, sizeof(cost.a));
memset(count.a, 0, sizeof(count.a));
}
for(int i = 0; i < q; ++i)
cout << ans[i] << endl;
return 0;
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:167:44: warning: unused variable 'v' [-Wunused-variable]
167 | int u = adj[periksa[i].se].fi, v = adj[periksa[i].se].se;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4308 KB |
Output is correct |
2 |
Correct |
3 ms |
4436 KB |
Output is correct |
3 |
Correct |
5 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4932 KB |
Output is correct |
5 |
Correct |
17 ms |
6408 KB |
Output is correct |
6 |
Correct |
24 ms |
7740 KB |
Output is correct |
7 |
Correct |
23 ms |
7660 KB |
Output is correct |
8 |
Correct |
19 ms |
6348 KB |
Output is correct |
9 |
Correct |
19 ms |
6412 KB |
Output is correct |
10 |
Correct |
19 ms |
6392 KB |
Output is correct |
11 |
Correct |
18 ms |
6288 KB |
Output is correct |
12 |
Correct |
18 ms |
6236 KB |
Output is correct |
13 |
Correct |
17 ms |
5972 KB |
Output is correct |
14 |
Correct |
18 ms |
5972 KB |
Output is correct |
15 |
Correct |
19 ms |
5932 KB |
Output is correct |
16 |
Correct |
19 ms |
5912 KB |
Output is correct |
17 |
Correct |
20 ms |
5904 KB |
Output is correct |
18 |
Correct |
19 ms |
6044 KB |
Output is correct |
19 |
Correct |
22 ms |
7784 KB |
Output is correct |
20 |
Correct |
22 ms |
7820 KB |
Output is correct |
21 |
Correct |
22 ms |
7832 KB |
Output is correct |
22 |
Correct |
21 ms |
7728 KB |
Output is correct |
23 |
Correct |
17 ms |
6244 KB |
Output is correct |
24 |
Correct |
17 ms |
6300 KB |
Output is correct |
25 |
Correct |
18 ms |
6640 KB |
Output is correct |
26 |
Correct |
14 ms |
6168 KB |
Output is correct |
27 |
Correct |
15 ms |
6336 KB |
Output is correct |
28 |
Correct |
19 ms |
6396 KB |
Output is correct |
29 |
Correct |
26 ms |
9828 KB |
Output is correct |
30 |
Correct |
18 ms |
6356 KB |
Output is correct |
31 |
Correct |
18 ms |
6348 KB |
Output is correct |
32 |
Correct |
18 ms |
6328 KB |
Output is correct |
33 |
Correct |
15 ms |
6036 KB |
Output is correct |
34 |
Correct |
15 ms |
5992 KB |
Output is correct |
35 |
Correct |
15 ms |
6040 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4436 KB |
Output is correct |
2 |
Correct |
18 ms |
6348 KB |
Output is correct |
3 |
Correct |
18 ms |
6352 KB |
Output is correct |
4 |
Correct |
18 ms |
6336 KB |
Output is correct |
5 |
Correct |
1147 ms |
80076 KB |
Output is correct |
6 |
Correct |
1216 ms |
109968 KB |
Output is correct |
7 |
Correct |
1275 ms |
102380 KB |
Output is correct |
8 |
Correct |
1027 ms |
84832 KB |
Output is correct |
9 |
Correct |
976 ms |
76404 KB |
Output is correct |
10 |
Correct |
1572 ms |
111852 KB |
Output is correct |
11 |
Correct |
1492 ms |
111876 KB |
Output is correct |
12 |
Correct |
1730 ms |
111368 KB |
Output is correct |
13 |
Correct |
1628 ms |
112020 KB |
Output is correct |
14 |
Correct |
1718 ms |
111236 KB |
Output is correct |
15 |
Correct |
1904 ms |
113476 KB |
Output is correct |
16 |
Correct |
2120 ms |
114304 KB |
Output is correct |
17 |
Correct |
1817 ms |
112736 KB |
Output is correct |
18 |
Correct |
2097 ms |
113788 KB |
Output is correct |
19 |
Correct |
2156 ms |
113492 KB |
Output is correct |
20 |
Correct |
2051 ms |
114732 KB |
Output is correct |
21 |
Correct |
1213 ms |
115940 KB |
Output is correct |
22 |
Correct |
1229 ms |
117116 KB |
Output is correct |
23 |
Correct |
1242 ms |
116756 KB |
Output is correct |
24 |
Correct |
1221 ms |
116036 KB |
Output is correct |
25 |
Correct |
1304 ms |
110596 KB |
Output is correct |
26 |
Correct |
1167 ms |
109604 KB |
Output is correct |
27 |
Correct |
1285 ms |
111760 KB |
Output is correct |
28 |
Correct |
671 ms |
112140 KB |
Output is correct |
29 |
Correct |
652 ms |
109192 KB |
Output is correct |
30 |
Correct |
839 ms |
103180 KB |
Output is correct |
31 |
Correct |
843 ms |
103448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4936 KB |
Output is correct |
2 |
Correct |
15 ms |
6048 KB |
Output is correct |
3 |
Correct |
15 ms |
5964 KB |
Output is correct |
4 |
Correct |
15 ms |
5916 KB |
Output is correct |
5 |
Correct |
954 ms |
85456 KB |
Output is correct |
6 |
Correct |
1039 ms |
89800 KB |
Output is correct |
7 |
Correct |
1049 ms |
95284 KB |
Output is correct |
8 |
Correct |
1514 ms |
114356 KB |
Output is correct |
9 |
Correct |
1484 ms |
114336 KB |
Output is correct |
10 |
Correct |
1558 ms |
114624 KB |
Output is correct |
11 |
Correct |
979 ms |
114740 KB |
Output is correct |
12 |
Correct |
972 ms |
114336 KB |
Output is correct |
13 |
Correct |
970 ms |
114600 KB |
Output is correct |
14 |
Correct |
557 ms |
115796 KB |
Output is correct |
15 |
Correct |
544 ms |
116728 KB |
Output is correct |
16 |
Correct |
805 ms |
115472 KB |
Output is correct |
17 |
Correct |
786 ms |
115736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4308 KB |
Output is correct |
2 |
Correct |
3 ms |
4436 KB |
Output is correct |
3 |
Correct |
5 ms |
4992 KB |
Output is correct |
4 |
Correct |
5 ms |
4932 KB |
Output is correct |
5 |
Correct |
17 ms |
6408 KB |
Output is correct |
6 |
Correct |
24 ms |
7740 KB |
Output is correct |
7 |
Correct |
23 ms |
7660 KB |
Output is correct |
8 |
Correct |
19 ms |
6348 KB |
Output is correct |
9 |
Correct |
19 ms |
6412 KB |
Output is correct |
10 |
Correct |
19 ms |
6392 KB |
Output is correct |
11 |
Correct |
18 ms |
6288 KB |
Output is correct |
12 |
Correct |
18 ms |
6236 KB |
Output is correct |
13 |
Correct |
17 ms |
5972 KB |
Output is correct |
14 |
Correct |
18 ms |
5972 KB |
Output is correct |
15 |
Correct |
19 ms |
5932 KB |
Output is correct |
16 |
Correct |
19 ms |
5912 KB |
Output is correct |
17 |
Correct |
20 ms |
5904 KB |
Output is correct |
18 |
Correct |
19 ms |
6044 KB |
Output is correct |
19 |
Correct |
22 ms |
7784 KB |
Output is correct |
20 |
Correct |
22 ms |
7820 KB |
Output is correct |
21 |
Correct |
22 ms |
7832 KB |
Output is correct |
22 |
Correct |
21 ms |
7728 KB |
Output is correct |
23 |
Correct |
17 ms |
6244 KB |
Output is correct |
24 |
Correct |
17 ms |
6300 KB |
Output is correct |
25 |
Correct |
18 ms |
6640 KB |
Output is correct |
26 |
Correct |
14 ms |
6168 KB |
Output is correct |
27 |
Correct |
15 ms |
6336 KB |
Output is correct |
28 |
Correct |
19 ms |
6396 KB |
Output is correct |
29 |
Correct |
26 ms |
9828 KB |
Output is correct |
30 |
Correct |
18 ms |
6356 KB |
Output is correct |
31 |
Correct |
18 ms |
6348 KB |
Output is correct |
32 |
Correct |
18 ms |
6328 KB |
Output is correct |
33 |
Correct |
15 ms |
6036 KB |
Output is correct |
34 |
Correct |
15 ms |
5992 KB |
Output is correct |
35 |
Correct |
15 ms |
6040 KB |
Output is correct |
36 |
Correct |
3 ms |
4436 KB |
Output is correct |
37 |
Correct |
18 ms |
6348 KB |
Output is correct |
38 |
Correct |
18 ms |
6352 KB |
Output is correct |
39 |
Correct |
18 ms |
6336 KB |
Output is correct |
40 |
Correct |
1147 ms |
80076 KB |
Output is correct |
41 |
Correct |
1216 ms |
109968 KB |
Output is correct |
42 |
Correct |
1275 ms |
102380 KB |
Output is correct |
43 |
Correct |
1027 ms |
84832 KB |
Output is correct |
44 |
Correct |
976 ms |
76404 KB |
Output is correct |
45 |
Correct |
1572 ms |
111852 KB |
Output is correct |
46 |
Correct |
1492 ms |
111876 KB |
Output is correct |
47 |
Correct |
1730 ms |
111368 KB |
Output is correct |
48 |
Correct |
1628 ms |
112020 KB |
Output is correct |
49 |
Correct |
1718 ms |
111236 KB |
Output is correct |
50 |
Correct |
1904 ms |
113476 KB |
Output is correct |
51 |
Correct |
2120 ms |
114304 KB |
Output is correct |
52 |
Correct |
1817 ms |
112736 KB |
Output is correct |
53 |
Correct |
2097 ms |
113788 KB |
Output is correct |
54 |
Correct |
2156 ms |
113492 KB |
Output is correct |
55 |
Correct |
2051 ms |
114732 KB |
Output is correct |
56 |
Correct |
1213 ms |
115940 KB |
Output is correct |
57 |
Correct |
1229 ms |
117116 KB |
Output is correct |
58 |
Correct |
1242 ms |
116756 KB |
Output is correct |
59 |
Correct |
1221 ms |
116036 KB |
Output is correct |
60 |
Correct |
1304 ms |
110596 KB |
Output is correct |
61 |
Correct |
1167 ms |
109604 KB |
Output is correct |
62 |
Correct |
1285 ms |
111760 KB |
Output is correct |
63 |
Correct |
671 ms |
112140 KB |
Output is correct |
64 |
Correct |
652 ms |
109192 KB |
Output is correct |
65 |
Correct |
839 ms |
103180 KB |
Output is correct |
66 |
Correct |
843 ms |
103448 KB |
Output is correct |
67 |
Correct |
4 ms |
4936 KB |
Output is correct |
68 |
Correct |
15 ms |
6048 KB |
Output is correct |
69 |
Correct |
15 ms |
5964 KB |
Output is correct |
70 |
Correct |
15 ms |
5916 KB |
Output is correct |
71 |
Correct |
954 ms |
85456 KB |
Output is correct |
72 |
Correct |
1039 ms |
89800 KB |
Output is correct |
73 |
Correct |
1049 ms |
95284 KB |
Output is correct |
74 |
Correct |
1514 ms |
114356 KB |
Output is correct |
75 |
Correct |
1484 ms |
114336 KB |
Output is correct |
76 |
Correct |
1558 ms |
114624 KB |
Output is correct |
77 |
Correct |
979 ms |
114740 KB |
Output is correct |
78 |
Correct |
972 ms |
114336 KB |
Output is correct |
79 |
Correct |
970 ms |
114600 KB |
Output is correct |
80 |
Correct |
557 ms |
115796 KB |
Output is correct |
81 |
Correct |
544 ms |
116728 KB |
Output is correct |
82 |
Correct |
805 ms |
115472 KB |
Output is correct |
83 |
Correct |
786 ms |
115736 KB |
Output is correct |
84 |
Correct |
1041 ms |
80716 KB |
Output is correct |
85 |
Correct |
1039 ms |
86548 KB |
Output is correct |
86 |
Correct |
963 ms |
90200 KB |
Output is correct |
87 |
Correct |
1693 ms |
111364 KB |
Output is correct |
88 |
Correct |
1616 ms |
111704 KB |
Output is correct |
89 |
Correct |
1665 ms |
112412 KB |
Output is correct |
90 |
Correct |
1679 ms |
112044 KB |
Output is correct |
91 |
Correct |
1648 ms |
112200 KB |
Output is correct |
92 |
Correct |
2011 ms |
112864 KB |
Output is correct |
93 |
Correct |
1873 ms |
112908 KB |
Output is correct |
94 |
Correct |
2124 ms |
113352 KB |
Output is correct |
95 |
Correct |
2044 ms |
113760 KB |
Output is correct |
96 |
Correct |
2098 ms |
113536 KB |
Output is correct |
97 |
Correct |
2420 ms |
113616 KB |
Output is correct |
98 |
Correct |
1780 ms |
116040 KB |
Output is correct |
99 |
Correct |
1739 ms |
114672 KB |
Output is correct |
100 |
Correct |
1634 ms |
115256 KB |
Output is correct |
101 |
Correct |
1619 ms |
115936 KB |
Output is correct |
102 |
Correct |
1665 ms |
111860 KB |
Output is correct |
103 |
Correct |
1514 ms |
111688 KB |
Output is correct |
104 |
Correct |
1328 ms |
112664 KB |
Output is correct |
105 |
Correct |
744 ms |
102940 KB |
Output is correct |
106 |
Correct |
721 ms |
105196 KB |
Output is correct |
107 |
Correct |
843 ms |
102096 KB |
Output is correct |
108 |
Correct |
858 ms |
102004 KB |
Output is correct |