#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define MAX 100010
#define MIN first
#define MAXNUM second
using namespace std;
using ll = long long;
int n, m, q;
int par[20][MAX], depth[MAX], in[MAX], out[MAX];
int max_h;
int dstep[MAX];
vector<int> graph[MAX];
int i, j;
struct spt {
ll s, e, val;
bool operator<(const spt& x) { return val < x.val; }
};
struct qu {
ll s, t, x, y;
};
vector<spt> v_spt;
vector<qu> v_q;
int l[MAX], r[MAX];
vector<pair<int, int>> arr;
void fastIO() {
ios::sync_with_stdio(false); cin.tie(0);
}
//euler tour trick.
int i_ett, i_order;
void ETT(int curr, int dep) {
dstep[curr] = ++i_order; in[curr] = ++i_ett; depth[curr] = dep;
for (int next : graph[curr]) {
if (in[next]) continue;
par[0][next] = curr;
ETT(next, dep + 1);
}
i_ett++;
out[curr] = i_ett;
}
//get parent based on sparse table.
void getParent() {
int tmp = n, cnt = 0;
while (tmp > 1) { tmp >>= 1; cnt++; }
max_h = cnt;
for (int h = 1; h <= max_h; h++) {
for (int x = 2; x <= n; x++) {
if (par[h - 1][x]) { par[h][x] = par[h - 1][par[h - 1][x]]; }
}
}
}
int getLCA(int a, int b) {
if (depth[a] != depth[b]) {
if (depth[a] < depth[b]) { swap(a, b); }
int diff = depth[a] - depth[b];
for (j = 0; diff > 0; j++) {
if (diff & 1) { a = par[j][a]; }
diff >>= 1;
}
}
if (a != b) {
for (int k = max_h; k >= 0; k--) {
if (par[k][a] != 0 && par[k][a] != par[k][b]) {
a = par[k][a]; b = par[k][b];
}
}
a = par[0][a];
}
return a;
}
ll tree_cpt[8 * MAX], tree_first[8 * MAX], tree_cnt[8 * MAX];
void update(ll tree[], int curr, int start, int end, int idx, ll val) {
if (start == end) { tree[curr] += val; return; }
int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
if (idx <= mid) { update(tree, lidx, start, mid, idx, val); }
else { update(tree, ridx, mid + 1, end, idx, val); }
tree[curr] = tree[lidx] + tree[ridx];
}
ll getSum(ll tree[], int curr, int start, int end, int t_start, int t_end) {
if (end < t_start || t_end < start) { return 0; }
if (t_start <= start && end <= t_end) { return tree[curr]; }
int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
return getSum(tree, lidx, start, mid, t_start, t_end) + getSum(tree, ridx, mid + 1, end, t_start, t_end);
}
void reset(int start = 1, int end = i_ett, int curr = 1) {
tree_cpt[curr] = tree_cnt[curr] = 0;
if (start == end) { return; }
int mid = start + end >> 1;
reset(start, mid, curr << 1);
reset(mid + 1, end, curr << 1 | 1);
}
int ret[MAX], sum_sp[MAX], sum_cnt[MAX];
void input() {
cin >> n >> m >> q;
arr.resize(n);
int a, b;
for (i = 1; i <= n - 1; i++) {
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
arr[i] = { min(a, b), max(a,b) };
}
for (i = 1; i <= m; i++) {
cin >> a >> b;
v_spt.push_back({ arr[a].MIN, arr[a].MAXNUM, b });
}
sort(v_spt.begin(), v_spt.end());
v_q.resize(q);
for (i = 0; i < q; i++) {
cin >> v_q[i].s >> v_q[i].t >> v_q[i].x >> v_q[i].y;
}
}
void solve() {
for (i = 0; i < MAX; i++) { ret[i] = -1; }
ETT(1, 0);
getParent();
//pbs
for (i = 0; i < q; i++) { l[i] = -1, r[i] = m; }
for (i = 0; i < m; i++) {
int start = v_spt[i].s, end = v_spt[i].e;
if (in[end] <= in[start] && in[start] <= out[end]) swap(start, end);
update(tree_first, 1, 1, i_ett, in[end], 1);
update(tree_first, 1, 1, i_ett, out[end], -1);
}
for (i = 0; i < q; i++) {
int lca = getLCA(v_q[i].s, v_q[i].t);
sum_sp[i] = getSum(tree_first, 1, 1, i_ett, 1, in[v_q[i].s])
+ getSum(tree_first, 1, 1, i_ett, 1, in[v_q[i].t])
- 2 * getSum(tree_first, 1, 1, i_ett, 1, in[lca]);
}
while (true) {
for (i = 0; i < MAX; i++) {
graph[i].clear();
}
reset();
bool flag = false;
for (i = 0; i < q; i++) {
if (l[i] + 1 == r[i]) continue;
flag = true; graph[l[i] + r[i] >> 1].push_back(i);
}
if (!flag) break;
for (i = 0; i < m; i++) {
ll start = v_spt[i].s, end = v_spt[i].e, v = v_spt[i].val;
if (in[end] <= in[start] && in[start] <= out[end]) { swap(start, end); }
update(tree_cpt, 1, 1, i_ett, in[end], v);
update(tree_cpt, 1, 1, i_ett, out[end], -v);
update(tree_cnt, 1, 1, i_ett, in[end], 1);
update(tree_cnt, 1, 1, i_ett, out[end], -1);
for (int next : graph[i]) {
int lca = getLCA(v_q[next].s, v_q[next].t);
ll currSp = getSum(tree_cpt, 1, 1, i_ett, 1, in[v_q[next].s])
+ getSum(tree_cpt, 1, 1, i_ett, 1, in[v_q[next].t])
- 2 * getSum(tree_cpt, 1, 1, i_ett, 1, in[lca]);
ll currCnt = getSum(tree_cnt, 1, 1, i_ett, 1, in[v_q[next].s])
+ getSum(tree_cnt, 1, 1, i_ett, 1, in[v_q[next].t])
- 2 * getSum(tree_cnt, 1, 1, i_ett, 1, in[lca]);
if (currSp <= v_q[next].y) {
ret[next] = max((ll)ret[next], v_q[next].x - sum_sp[next] + currCnt);
l[next] = i;
}
else { r[next] = i; }
}
}
}
for (i = 0; i < q; i++) {
if (ret[i] == -1 && v_q[i].x >= sum_sp[i]) {
ret[i] = v_q[i].x - sum_sp[i];
}
cout << ret[i] << '\n';
}
}
int main() {
fastIO();
input();
solve();
return 0;
}
Compilation message
currencies.cpp: In function 'void update(ll*, int, int, int, int, ll)':
currencies.cpp:84:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
| ~~~~~~^~~~~
currencies.cpp: In function 'll getSum(ll*, int, int, int, int, int)':
currencies.cpp:93:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
93 | int lidx = curr << 1, ridx = lidx | 1, mid = start + end >> 1;
| ~~~~~~^~~~~
currencies.cpp: In function 'void reset(int, int, int)':
currencies.cpp:100:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
100 | int mid = start + end >> 1;
| ~~~~~~^~~~~
currencies.cpp: In function 'void solve()':
currencies.cpp:161:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
161 | flag = true; graph[l[i] + r[i] >> 1].push_back(i);
| ~~~~~^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12636 KB |
Output is correct |
2 |
Correct |
2 ms |
12636 KB |
Output is correct |
3 |
Correct |
2 ms |
12784 KB |
Output is correct |
4 |
Correct |
3 ms |
12636 KB |
Output is correct |
5 |
Correct |
18 ms |
12888 KB |
Output is correct |
6 |
Correct |
22 ms |
13148 KB |
Output is correct |
7 |
Correct |
18 ms |
13100 KB |
Output is correct |
8 |
Correct |
23 ms |
13140 KB |
Output is correct |
9 |
Correct |
23 ms |
13148 KB |
Output is correct |
10 |
Correct |
23 ms |
13152 KB |
Output is correct |
11 |
Correct |
27 ms |
13148 KB |
Output is correct |
12 |
Correct |
23 ms |
13104 KB |
Output is correct |
13 |
Correct |
24 ms |
15192 KB |
Output is correct |
14 |
Correct |
25 ms |
15196 KB |
Output is correct |
15 |
Correct |
25 ms |
15196 KB |
Output is correct |
16 |
Correct |
24 ms |
15180 KB |
Output is correct |
17 |
Correct |
25 ms |
15196 KB |
Output is correct |
18 |
Correct |
24 ms |
15196 KB |
Output is correct |
19 |
Correct |
21 ms |
13148 KB |
Output is correct |
20 |
Correct |
21 ms |
13136 KB |
Output is correct |
21 |
Correct |
24 ms |
13144 KB |
Output is correct |
22 |
Correct |
21 ms |
13148 KB |
Output is correct |
23 |
Correct |
17 ms |
13148 KB |
Output is correct |
24 |
Correct |
19 ms |
13148 KB |
Output is correct |
25 |
Correct |
18 ms |
13148 KB |
Output is correct |
26 |
Correct |
16 ms |
13148 KB |
Output is correct |
27 |
Correct |
15 ms |
13000 KB |
Output is correct |
28 |
Correct |
16 ms |
13148 KB |
Output is correct |
29 |
Correct |
17 ms |
13144 KB |
Output is correct |
30 |
Correct |
24 ms |
13136 KB |
Output is correct |
31 |
Correct |
22 ms |
13148 KB |
Output is correct |
32 |
Correct |
23 ms |
13148 KB |
Output is correct |
33 |
Correct |
26 ms |
15536 KB |
Output is correct |
34 |
Correct |
24 ms |
15192 KB |
Output is correct |
35 |
Correct |
24 ms |
15196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12632 KB |
Output is correct |
2 |
Correct |
23 ms |
13100 KB |
Output is correct |
3 |
Correct |
23 ms |
13148 KB |
Output is correct |
4 |
Correct |
23 ms |
13148 KB |
Output is correct |
5 |
Correct |
2057 ms |
40432 KB |
Output is correct |
6 |
Correct |
2238 ms |
43528 KB |
Output is correct |
7 |
Correct |
2270 ms |
42848 KB |
Output is correct |
8 |
Correct |
1729 ms |
39612 KB |
Output is correct |
9 |
Correct |
1709 ms |
39156 KB |
Output is correct |
10 |
Correct |
2852 ms |
45380 KB |
Output is correct |
11 |
Correct |
2806 ms |
45472 KB |
Output is correct |
12 |
Correct |
2828 ms |
46012 KB |
Output is correct |
13 |
Correct |
2831 ms |
45452 KB |
Output is correct |
14 |
Correct |
3041 ms |
45984 KB |
Output is correct |
15 |
Correct |
3506 ms |
52860 KB |
Output is correct |
16 |
Correct |
3555 ms |
53720 KB |
Output is correct |
17 |
Correct |
3474 ms |
52736 KB |
Output is correct |
18 |
Correct |
3159 ms |
47528 KB |
Output is correct |
19 |
Correct |
3390 ms |
47468 KB |
Output is correct |
20 |
Correct |
3210 ms |
47260 KB |
Output is correct |
21 |
Correct |
2629 ms |
43568 KB |
Output is correct |
22 |
Correct |
2690 ms |
43332 KB |
Output is correct |
23 |
Correct |
2831 ms |
43380 KB |
Output is correct |
24 |
Correct |
2708 ms |
44056 KB |
Output is correct |
25 |
Correct |
2122 ms |
45172 KB |
Output is correct |
26 |
Correct |
2182 ms |
45292 KB |
Output is correct |
27 |
Correct |
1945 ms |
45180 KB |
Output is correct |
28 |
Correct |
1540 ms |
46484 KB |
Output is correct |
29 |
Correct |
1386 ms |
44740 KB |
Output is correct |
30 |
Correct |
1623 ms |
45016 KB |
Output is correct |
31 |
Correct |
1760 ms |
44540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12636 KB |
Output is correct |
2 |
Correct |
24 ms |
15192 KB |
Output is correct |
3 |
Correct |
24 ms |
15196 KB |
Output is correct |
4 |
Correct |
23 ms |
15196 KB |
Output is correct |
5 |
Correct |
1988 ms |
48324 KB |
Output is correct |
6 |
Correct |
1977 ms |
47888 KB |
Output is correct |
7 |
Correct |
2293 ms |
41176 KB |
Output is correct |
8 |
Correct |
3524 ms |
53848 KB |
Output is correct |
9 |
Correct |
3243 ms |
53584 KB |
Output is correct |
10 |
Correct |
3584 ms |
54196 KB |
Output is correct |
11 |
Correct |
2367 ms |
53596 KB |
Output is correct |
12 |
Correct |
2603 ms |
53636 KB |
Output is correct |
13 |
Correct |
2468 ms |
53540 KB |
Output is correct |
14 |
Correct |
1667 ms |
53720 KB |
Output is correct |
15 |
Correct |
1804 ms |
54652 KB |
Output is correct |
16 |
Correct |
2119 ms |
53712 KB |
Output is correct |
17 |
Correct |
2246 ms |
53684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
12636 KB |
Output is correct |
2 |
Correct |
2 ms |
12636 KB |
Output is correct |
3 |
Correct |
2 ms |
12784 KB |
Output is correct |
4 |
Correct |
3 ms |
12636 KB |
Output is correct |
5 |
Correct |
18 ms |
12888 KB |
Output is correct |
6 |
Correct |
22 ms |
13148 KB |
Output is correct |
7 |
Correct |
18 ms |
13100 KB |
Output is correct |
8 |
Correct |
23 ms |
13140 KB |
Output is correct |
9 |
Correct |
23 ms |
13148 KB |
Output is correct |
10 |
Correct |
23 ms |
13152 KB |
Output is correct |
11 |
Correct |
27 ms |
13148 KB |
Output is correct |
12 |
Correct |
23 ms |
13104 KB |
Output is correct |
13 |
Correct |
24 ms |
15192 KB |
Output is correct |
14 |
Correct |
25 ms |
15196 KB |
Output is correct |
15 |
Correct |
25 ms |
15196 KB |
Output is correct |
16 |
Correct |
24 ms |
15180 KB |
Output is correct |
17 |
Correct |
25 ms |
15196 KB |
Output is correct |
18 |
Correct |
24 ms |
15196 KB |
Output is correct |
19 |
Correct |
21 ms |
13148 KB |
Output is correct |
20 |
Correct |
21 ms |
13136 KB |
Output is correct |
21 |
Correct |
24 ms |
13144 KB |
Output is correct |
22 |
Correct |
21 ms |
13148 KB |
Output is correct |
23 |
Correct |
17 ms |
13148 KB |
Output is correct |
24 |
Correct |
19 ms |
13148 KB |
Output is correct |
25 |
Correct |
18 ms |
13148 KB |
Output is correct |
26 |
Correct |
16 ms |
13148 KB |
Output is correct |
27 |
Correct |
15 ms |
13000 KB |
Output is correct |
28 |
Correct |
16 ms |
13148 KB |
Output is correct |
29 |
Correct |
17 ms |
13144 KB |
Output is correct |
30 |
Correct |
24 ms |
13136 KB |
Output is correct |
31 |
Correct |
22 ms |
13148 KB |
Output is correct |
32 |
Correct |
23 ms |
13148 KB |
Output is correct |
33 |
Correct |
26 ms |
15536 KB |
Output is correct |
34 |
Correct |
24 ms |
15192 KB |
Output is correct |
35 |
Correct |
24 ms |
15196 KB |
Output is correct |
36 |
Correct |
2 ms |
12632 KB |
Output is correct |
37 |
Correct |
23 ms |
13100 KB |
Output is correct |
38 |
Correct |
23 ms |
13148 KB |
Output is correct |
39 |
Correct |
23 ms |
13148 KB |
Output is correct |
40 |
Correct |
2057 ms |
40432 KB |
Output is correct |
41 |
Correct |
2238 ms |
43528 KB |
Output is correct |
42 |
Correct |
2270 ms |
42848 KB |
Output is correct |
43 |
Correct |
1729 ms |
39612 KB |
Output is correct |
44 |
Correct |
1709 ms |
39156 KB |
Output is correct |
45 |
Correct |
2852 ms |
45380 KB |
Output is correct |
46 |
Correct |
2806 ms |
45472 KB |
Output is correct |
47 |
Correct |
2828 ms |
46012 KB |
Output is correct |
48 |
Correct |
2831 ms |
45452 KB |
Output is correct |
49 |
Correct |
3041 ms |
45984 KB |
Output is correct |
50 |
Correct |
3506 ms |
52860 KB |
Output is correct |
51 |
Correct |
3555 ms |
53720 KB |
Output is correct |
52 |
Correct |
3474 ms |
52736 KB |
Output is correct |
53 |
Correct |
3159 ms |
47528 KB |
Output is correct |
54 |
Correct |
3390 ms |
47468 KB |
Output is correct |
55 |
Correct |
3210 ms |
47260 KB |
Output is correct |
56 |
Correct |
2629 ms |
43568 KB |
Output is correct |
57 |
Correct |
2690 ms |
43332 KB |
Output is correct |
58 |
Correct |
2831 ms |
43380 KB |
Output is correct |
59 |
Correct |
2708 ms |
44056 KB |
Output is correct |
60 |
Correct |
2122 ms |
45172 KB |
Output is correct |
61 |
Correct |
2182 ms |
45292 KB |
Output is correct |
62 |
Correct |
1945 ms |
45180 KB |
Output is correct |
63 |
Correct |
1540 ms |
46484 KB |
Output is correct |
64 |
Correct |
1386 ms |
44740 KB |
Output is correct |
65 |
Correct |
1623 ms |
45016 KB |
Output is correct |
66 |
Correct |
1760 ms |
44540 KB |
Output is correct |
67 |
Correct |
2 ms |
12636 KB |
Output is correct |
68 |
Correct |
24 ms |
15192 KB |
Output is correct |
69 |
Correct |
24 ms |
15196 KB |
Output is correct |
70 |
Correct |
23 ms |
15196 KB |
Output is correct |
71 |
Correct |
1988 ms |
48324 KB |
Output is correct |
72 |
Correct |
1977 ms |
47888 KB |
Output is correct |
73 |
Correct |
2293 ms |
41176 KB |
Output is correct |
74 |
Correct |
3524 ms |
53848 KB |
Output is correct |
75 |
Correct |
3243 ms |
53584 KB |
Output is correct |
76 |
Correct |
3584 ms |
54196 KB |
Output is correct |
77 |
Correct |
2367 ms |
53596 KB |
Output is correct |
78 |
Correct |
2603 ms |
53636 KB |
Output is correct |
79 |
Correct |
2468 ms |
53540 KB |
Output is correct |
80 |
Correct |
1667 ms |
53720 KB |
Output is correct |
81 |
Correct |
1804 ms |
54652 KB |
Output is correct |
82 |
Correct |
2119 ms |
53712 KB |
Output is correct |
83 |
Correct |
2246 ms |
53684 KB |
Output is correct |
84 |
Correct |
2033 ms |
40320 KB |
Output is correct |
85 |
Correct |
1732 ms |
34672 KB |
Output is correct |
86 |
Correct |
1533 ms |
34216 KB |
Output is correct |
87 |
Correct |
2737 ms |
45784 KB |
Output is correct |
88 |
Correct |
2776 ms |
45500 KB |
Output is correct |
89 |
Correct |
2793 ms |
45508 KB |
Output is correct |
90 |
Correct |
2792 ms |
45572 KB |
Output is correct |
91 |
Correct |
3045 ms |
45508 KB |
Output is correct |
92 |
Correct |
3812 ms |
51736 KB |
Output is correct |
93 |
Correct |
3538 ms |
52212 KB |
Output is correct |
94 |
Correct |
3229 ms |
47276 KB |
Output is correct |
95 |
Correct |
3107 ms |
47696 KB |
Output is correct |
96 |
Correct |
3136 ms |
47776 KB |
Output is correct |
97 |
Correct |
3282 ms |
47700 KB |
Output is correct |
98 |
Correct |
2617 ms |
44096 KB |
Output is correct |
99 |
Correct |
2504 ms |
43408 KB |
Output is correct |
100 |
Correct |
2543 ms |
43688 KB |
Output is correct |
101 |
Correct |
2457 ms |
43508 KB |
Output is correct |
102 |
Correct |
2028 ms |
45068 KB |
Output is correct |
103 |
Correct |
2045 ms |
45400 KB |
Output is correct |
104 |
Correct |
2061 ms |
45136 KB |
Output is correct |
105 |
Correct |
1544 ms |
44992 KB |
Output is correct |
106 |
Correct |
1420 ms |
45900 KB |
Output is correct |
107 |
Correct |
1657 ms |
44304 KB |
Output is correct |
108 |
Correct |
1828 ms |
44336 KB |
Output is correct |