#include <bits/stdc++.h>
#define MAX 100005
#define MOD 998244353
#define INF (ll)(1e18)
#define inf (1987654321)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef complex<long double> cpx;
constexpr long double PI = acos(-1);
int tt, n, m, k, q;
int in[MAX], out[MAX], dep[MAX];
int parent[MAX][20];
int lo[MAX], hi[MAX];
int ans[MAX];
vector<pii> edge;
vector<pii> chkpoint;
vector<pair<pii, pll> > inp;
vector<int> graph[MAX];
vector<int> event[MAX];
ll seg[MAX << 2];
void init(int str, int ed, int node) {
seg[node] = 0;
if(str == ed) return;
int mid = str + ed >> 1;
init(str, mid, node << 1);
init(mid + 1, ed, node << 1 | 1);
}
void update(int str, int ed, int left, int right, ll val, int node) {
if(str > right || ed < left) return;
if(left <= str && ed <= right) {
seg[node] += val;
return;
}
int mid = str + ed >> 1;
update(str, mid, left, right, val, node << 1);
update(mid + 1, ed, left, right, val, node << 1 | 1);
}
ll query(int str, int ed, int idx, int node) {
if(str == ed) return seg[node];
int mid = str + ed >> 1;
if(idx <= mid) return query(str, mid, idx, node << 1) + seg[node];
else return query(mid + 1, ed, idx, node << 1 | 1) + seg[node];
}
int pv = 0;
void dfs(int node, int par) {
parent[node][0] = par; in[node] = ++pv;
for(auto v : graph[node]) {
if(v == par) continue;
dep[v] = dep[node] + 1;
dfs(v, node);
}
out[node] = pv;
}
int lca(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
int diff = dep[a] - dep[b], j = 0;
while(diff) {
if(diff & 1) a = parent[a][j];
diff >>= 1; ++j;
}
if(a == b) return a;
for(int i = 19; i >= 0; --i) {
if(parent[a][i] == parent[b][i]) continue;
a = parent[a][i];
b = parent[b][i];
}
return parent[a][0];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> q;
edge.resize(n - 1);
for(int i = 0; i < n - 1; ++i) {
int a, b; cin >> a >> b;
edge[i] = {a, b};
graph[a].push_back(b);
graph[b].push_back(a);
}
chkpoint.resize(m);
for(int i = 0; i < m; ++i) cin >> chkpoint[i].second >> chkpoint[i].first;
for(int i = 0; i < m; ++i) chkpoint[i].second--;
sort(chkpoint.begin(), chkpoint.end());
inp.resize(q);
for(int i = 0; i < q; ++i) cin >> inp[i].first.first >> inp[i].first.second >> inp[i].second.first >> inp[i].second.second;
for(int i = 0; i < q; ++i) lo[i] = -1, hi[i] = m;
dfs(1, 0);
for(int j = 1; j < 20; ++j) for(int i = 1; i <= n; ++i) parent[i][j] = parent[parent[i][j - 1]][j - 1];
while(true) {
int flag = 1;
for(int i = 0; i < m; ++i) event[i].clear();
for(int i = 0; i < q; ++i) {
if(lo[i] + 1 == hi[i]) continue;
flag = 0;
int mid = lo[i] + hi[i] >> 1;
event[mid].push_back(i);
}
if(flag) break;
init(1, n, 1);
for(int i = 0; i < m; ++i) {
int j = chkpoint[i].second;
int u = edge[j].first, v = edge[j].second;
if(dep[u] < dep[v]) swap(u, v);
update(1, n, in[u], out[u], chkpoint[i].first, 1);
for(auto k : event[i]) {
int a = inp[k].first.first, b = inp[k].first.second;
int p = lca(a, b);
ll sum = query(1, n, in[a], 1);
sum += query(1, n, in[b], 1);
sum -= 2 * query(1, n, in[p], 1);
if(sum <= inp[k].second.second) lo[k] = i;
else hi[k] = i;
}
}
}
for(int i = 0; i < m; ++i) event[i].clear();
for(int i = 0; i < q; ++i) {
if(lo[i] == -1) continue;
event[lo[i]].push_back(i);
}
init(1, n, 1);
for(int i = m - 1; i >= 0; --i) {
for(auto k : event[i]) {
int a = inp[k].first.first, b = inp[k].first.second;
int p = lca(a, b);
ll sum = query(1, n, in[a], 1);
sum += query(1, n, in[b], 1);
sum -= 2 * query(1, n, in[p], 1);
if(sum <= inp[k].second.first) ans[k] = inp[k].second.first - sum;
else ans[k] = -1;
}
int j = chkpoint[i].second;
int u = edge[j].first, v = edge[j].second;
if(dep[u] < dep[v]) swap(u, v);
update(1, n, in[u], out[u], 1, 1);
}
for(int i = 0; i < q; ++i) {
if(lo[i] != -1) continue;
int a = inp[i].first.first, b = inp[i].first.second;
int p = lca(a, b);
ll sum = query(1, n, in[a], 1);
sum += query(1, n, in[b], 1);
sum -= 2 * query(1, n, in[p], 1);
if(sum <= inp[i].second.first) ans[i] = inp[i].second.first - sum;
else ans[i] = -1;
}
for(int i = 0; i < q; ++i) cout << ans[i] << '\n';
return 0;
}
Compilation message
currencies.cpp: In function 'void init(int, int, int)':
currencies.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid = str + ed >> 1;
| ~~~~^~~~
currencies.cpp: In function 'void update(int, int, int, int, ll, int)':
currencies.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = str + ed >> 1;
| ~~~~^~~~
currencies.cpp: In function 'll query(int, int, int, int)':
currencies.cpp:50:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid = str + ed >> 1;
| ~~~~^~~~
currencies.cpp: In function 'int main()':
currencies.cpp:114:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
114 | int mid = lo[i] + hi[i] >> 1;
| ~~~~~~^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
2 ms |
8540 KB |
Output is correct |
5 |
Correct |
8 ms |
8796 KB |
Output is correct |
6 |
Correct |
11 ms |
9052 KB |
Output is correct |
7 |
Correct |
9 ms |
9052 KB |
Output is correct |
8 |
Correct |
11 ms |
9104 KB |
Output is correct |
9 |
Correct |
11 ms |
8924 KB |
Output is correct |
10 |
Correct |
11 ms |
9052 KB |
Output is correct |
11 |
Correct |
11 ms |
9052 KB |
Output is correct |
12 |
Correct |
11 ms |
9088 KB |
Output is correct |
13 |
Correct |
11 ms |
9052 KB |
Output is correct |
14 |
Correct |
12 ms |
9052 KB |
Output is correct |
15 |
Correct |
12 ms |
9052 KB |
Output is correct |
16 |
Correct |
13 ms |
9052 KB |
Output is correct |
17 |
Correct |
13 ms |
9148 KB |
Output is correct |
18 |
Correct |
13 ms |
9052 KB |
Output is correct |
19 |
Correct |
10 ms |
9052 KB |
Output is correct |
20 |
Correct |
10 ms |
9064 KB |
Output is correct |
21 |
Correct |
11 ms |
9068 KB |
Output is correct |
22 |
Correct |
10 ms |
9052 KB |
Output is correct |
23 |
Correct |
9 ms |
9052 KB |
Output is correct |
24 |
Correct |
10 ms |
9048 KB |
Output is correct |
25 |
Correct |
9 ms |
9048 KB |
Output is correct |
26 |
Correct |
8 ms |
9052 KB |
Output is correct |
27 |
Correct |
8 ms |
9052 KB |
Output is correct |
28 |
Correct |
8 ms |
9052 KB |
Output is correct |
29 |
Correct |
11 ms |
8940 KB |
Output is correct |
30 |
Correct |
13 ms |
9052 KB |
Output is correct |
31 |
Correct |
11 ms |
9052 KB |
Output is correct |
32 |
Correct |
11 ms |
9052 KB |
Output is correct |
33 |
Correct |
11 ms |
9052 KB |
Output is correct |
34 |
Correct |
12 ms |
9052 KB |
Output is correct |
35 |
Correct |
11 ms |
9188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8540 KB |
Output is correct |
2 |
Correct |
11 ms |
8796 KB |
Output is correct |
3 |
Correct |
11 ms |
9028 KB |
Output is correct |
4 |
Correct |
11 ms |
9016 KB |
Output is correct |
5 |
Correct |
783 ms |
34948 KB |
Output is correct |
6 |
Correct |
1070 ms |
35792 KB |
Output is correct |
7 |
Correct |
883 ms |
37108 KB |
Output is correct |
8 |
Correct |
657 ms |
33580 KB |
Output is correct |
9 |
Correct |
719 ms |
33336 KB |
Output is correct |
10 |
Correct |
1186 ms |
41072 KB |
Output is correct |
11 |
Correct |
1197 ms |
40764 KB |
Output is correct |
12 |
Correct |
1336 ms |
40808 KB |
Output is correct |
13 |
Correct |
1292 ms |
40652 KB |
Output is correct |
14 |
Correct |
1160 ms |
40804 KB |
Output is correct |
15 |
Correct |
1627 ms |
47392 KB |
Output is correct |
16 |
Correct |
1550 ms |
47680 KB |
Output is correct |
17 |
Correct |
1579 ms |
46936 KB |
Output is correct |
18 |
Correct |
1548 ms |
41204 KB |
Output is correct |
19 |
Correct |
1607 ms |
41116 KB |
Output is correct |
20 |
Correct |
1640 ms |
41412 KB |
Output is correct |
21 |
Correct |
1020 ms |
41020 KB |
Output is correct |
22 |
Correct |
1029 ms |
41060 KB |
Output is correct |
23 |
Correct |
959 ms |
41376 KB |
Output is correct |
24 |
Correct |
972 ms |
41620 KB |
Output is correct |
25 |
Correct |
949 ms |
40780 KB |
Output is correct |
26 |
Correct |
983 ms |
40648 KB |
Output is correct |
27 |
Correct |
919 ms |
41060 KB |
Output is correct |
28 |
Correct |
593 ms |
39624 KB |
Output is correct |
29 |
Correct |
577 ms |
38580 KB |
Output is correct |
30 |
Correct |
727 ms |
39388 KB |
Output is correct |
31 |
Correct |
706 ms |
39120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
8540 KB |
Output is correct |
2 |
Correct |
11 ms |
9052 KB |
Output is correct |
3 |
Correct |
11 ms |
9052 KB |
Output is correct |
4 |
Correct |
11 ms |
9068 KB |
Output is correct |
5 |
Correct |
865 ms |
36332 KB |
Output is correct |
6 |
Correct |
1136 ms |
35976 KB |
Output is correct |
7 |
Correct |
1087 ms |
32572 KB |
Output is correct |
8 |
Correct |
1747 ms |
42124 KB |
Output is correct |
9 |
Correct |
1783 ms |
42308 KB |
Output is correct |
10 |
Correct |
1303 ms |
42436 KB |
Output is correct |
11 |
Correct |
1008 ms |
42180 KB |
Output is correct |
12 |
Correct |
1040 ms |
42380 KB |
Output is correct |
13 |
Correct |
1055 ms |
42220 KB |
Output is correct |
14 |
Correct |
613 ms |
41932 KB |
Output is correct |
15 |
Correct |
599 ms |
41144 KB |
Output is correct |
16 |
Correct |
878 ms |
41884 KB |
Output is correct |
17 |
Correct |
714 ms |
41672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
1 ms |
8540 KB |
Output is correct |
4 |
Correct |
2 ms |
8540 KB |
Output is correct |
5 |
Correct |
8 ms |
8796 KB |
Output is correct |
6 |
Correct |
11 ms |
9052 KB |
Output is correct |
7 |
Correct |
9 ms |
9052 KB |
Output is correct |
8 |
Correct |
11 ms |
9104 KB |
Output is correct |
9 |
Correct |
11 ms |
8924 KB |
Output is correct |
10 |
Correct |
11 ms |
9052 KB |
Output is correct |
11 |
Correct |
11 ms |
9052 KB |
Output is correct |
12 |
Correct |
11 ms |
9088 KB |
Output is correct |
13 |
Correct |
11 ms |
9052 KB |
Output is correct |
14 |
Correct |
12 ms |
9052 KB |
Output is correct |
15 |
Correct |
12 ms |
9052 KB |
Output is correct |
16 |
Correct |
13 ms |
9052 KB |
Output is correct |
17 |
Correct |
13 ms |
9148 KB |
Output is correct |
18 |
Correct |
13 ms |
9052 KB |
Output is correct |
19 |
Correct |
10 ms |
9052 KB |
Output is correct |
20 |
Correct |
10 ms |
9064 KB |
Output is correct |
21 |
Correct |
11 ms |
9068 KB |
Output is correct |
22 |
Correct |
10 ms |
9052 KB |
Output is correct |
23 |
Correct |
9 ms |
9052 KB |
Output is correct |
24 |
Correct |
10 ms |
9048 KB |
Output is correct |
25 |
Correct |
9 ms |
9048 KB |
Output is correct |
26 |
Correct |
8 ms |
9052 KB |
Output is correct |
27 |
Correct |
8 ms |
9052 KB |
Output is correct |
28 |
Correct |
8 ms |
9052 KB |
Output is correct |
29 |
Correct |
11 ms |
8940 KB |
Output is correct |
30 |
Correct |
13 ms |
9052 KB |
Output is correct |
31 |
Correct |
11 ms |
9052 KB |
Output is correct |
32 |
Correct |
11 ms |
9052 KB |
Output is correct |
33 |
Correct |
11 ms |
9052 KB |
Output is correct |
34 |
Correct |
12 ms |
9052 KB |
Output is correct |
35 |
Correct |
11 ms |
9188 KB |
Output is correct |
36 |
Correct |
2 ms |
8540 KB |
Output is correct |
37 |
Correct |
11 ms |
8796 KB |
Output is correct |
38 |
Correct |
11 ms |
9028 KB |
Output is correct |
39 |
Correct |
11 ms |
9016 KB |
Output is correct |
40 |
Correct |
783 ms |
34948 KB |
Output is correct |
41 |
Correct |
1070 ms |
35792 KB |
Output is correct |
42 |
Correct |
883 ms |
37108 KB |
Output is correct |
43 |
Correct |
657 ms |
33580 KB |
Output is correct |
44 |
Correct |
719 ms |
33336 KB |
Output is correct |
45 |
Correct |
1186 ms |
41072 KB |
Output is correct |
46 |
Correct |
1197 ms |
40764 KB |
Output is correct |
47 |
Correct |
1336 ms |
40808 KB |
Output is correct |
48 |
Correct |
1292 ms |
40652 KB |
Output is correct |
49 |
Correct |
1160 ms |
40804 KB |
Output is correct |
50 |
Correct |
1627 ms |
47392 KB |
Output is correct |
51 |
Correct |
1550 ms |
47680 KB |
Output is correct |
52 |
Correct |
1579 ms |
46936 KB |
Output is correct |
53 |
Correct |
1548 ms |
41204 KB |
Output is correct |
54 |
Correct |
1607 ms |
41116 KB |
Output is correct |
55 |
Correct |
1640 ms |
41412 KB |
Output is correct |
56 |
Correct |
1020 ms |
41020 KB |
Output is correct |
57 |
Correct |
1029 ms |
41060 KB |
Output is correct |
58 |
Correct |
959 ms |
41376 KB |
Output is correct |
59 |
Correct |
972 ms |
41620 KB |
Output is correct |
60 |
Correct |
949 ms |
40780 KB |
Output is correct |
61 |
Correct |
983 ms |
40648 KB |
Output is correct |
62 |
Correct |
919 ms |
41060 KB |
Output is correct |
63 |
Correct |
593 ms |
39624 KB |
Output is correct |
64 |
Correct |
577 ms |
38580 KB |
Output is correct |
65 |
Correct |
727 ms |
39388 KB |
Output is correct |
66 |
Correct |
706 ms |
39120 KB |
Output is correct |
67 |
Correct |
2 ms |
8540 KB |
Output is correct |
68 |
Correct |
11 ms |
9052 KB |
Output is correct |
69 |
Correct |
11 ms |
9052 KB |
Output is correct |
70 |
Correct |
11 ms |
9068 KB |
Output is correct |
71 |
Correct |
865 ms |
36332 KB |
Output is correct |
72 |
Correct |
1136 ms |
35976 KB |
Output is correct |
73 |
Correct |
1087 ms |
32572 KB |
Output is correct |
74 |
Correct |
1747 ms |
42124 KB |
Output is correct |
75 |
Correct |
1783 ms |
42308 KB |
Output is correct |
76 |
Correct |
1303 ms |
42436 KB |
Output is correct |
77 |
Correct |
1008 ms |
42180 KB |
Output is correct |
78 |
Correct |
1040 ms |
42380 KB |
Output is correct |
79 |
Correct |
1055 ms |
42220 KB |
Output is correct |
80 |
Correct |
613 ms |
41932 KB |
Output is correct |
81 |
Correct |
599 ms |
41144 KB |
Output is correct |
82 |
Correct |
878 ms |
41884 KB |
Output is correct |
83 |
Correct |
714 ms |
41672 KB |
Output is correct |
84 |
Correct |
903 ms |
34440 KB |
Output is correct |
85 |
Correct |
834 ms |
31776 KB |
Output is correct |
86 |
Correct |
724 ms |
31100 KB |
Output is correct |
87 |
Correct |
1382 ms |
40996 KB |
Output is correct |
88 |
Correct |
1290 ms |
40992 KB |
Output is correct |
89 |
Correct |
1261 ms |
40864 KB |
Output is correct |
90 |
Correct |
1223 ms |
40900 KB |
Output is correct |
91 |
Correct |
1265 ms |
40800 KB |
Output is correct |
92 |
Correct |
1751 ms |
45556 KB |
Output is correct |
93 |
Correct |
1632 ms |
46832 KB |
Output is correct |
94 |
Correct |
1811 ms |
41116 KB |
Output is correct |
95 |
Correct |
1688 ms |
41256 KB |
Output is correct |
96 |
Correct |
1914 ms |
41292 KB |
Output is correct |
97 |
Correct |
2123 ms |
41344 KB |
Output is correct |
98 |
Correct |
1253 ms |
41160 KB |
Output is correct |
99 |
Correct |
1215 ms |
40924 KB |
Output is correct |
100 |
Correct |
1241 ms |
41016 KB |
Output is correct |
101 |
Correct |
1382 ms |
41232 KB |
Output is correct |
102 |
Correct |
1162 ms |
41544 KB |
Output is correct |
103 |
Correct |
1082 ms |
41384 KB |
Output is correct |
104 |
Correct |
1068 ms |
41408 KB |
Output is correct |
105 |
Correct |
652 ms |
38828 KB |
Output is correct |
106 |
Correct |
647 ms |
39628 KB |
Output is correct |
107 |
Correct |
757 ms |
38572 KB |
Output is correct |
108 |
Correct |
768 ms |
38720 KB |
Output is correct |