//
// Created by 42kangaroo on 26/01/2024.
//
#include "bits/stdc++.h"
using namespace std;
#define int long long
using g_t = vector<vector<int>>;
struct SegAb {
int st, en, se;
};
struct Node {
int l, r, bl, br, numL, sumL;
};
struct PSegTe {
vector<Node> a;
vector<int> cooC;
int high;
int build(int l, int r) {
int act = a.size();
a.push_back({-1, -1, l, r, 0, 0});
if (l + 1 < r) {
int m = (l + r) / 2;
a[act].l = build(l, m);
a[act].r = build(m, r);
}
return act;
}
pair<int, int> get(int st, int k) {
if (a[st].br <= k) return {a[st].numL, a[st].sumL};
if (a[st].bl >= k) return {0, 0};
pair<int, int> res = {0, 0};
if (a[st].l != -1) {
auto re = get(a[st].l, k);
res.first += re.first;
res.second += re.second;
re = get(a[st].r, k);
res.first += re.first;
res.second += re.second;
}
return res;
}
int add(int st, int k, int v) {
if (a[st].bl > k || a[st].br <= k) return st;
int nN = a.size();
a.push_back({-1, -1, a[st].bl, a[st].br, 0, 0});
if (a[st].l != -1) {
a[nN].l = add(a[st].l, k, v);
a[nN].r = add(a[st].r, k, v);
a[nN].numL = a[a[nN].l].numL + a[a[nN].r].numL;
a[nN].sumL = a[a[nN].l].sumL + a[a[nN].r].sumL;
} else {
a[nN].numL = a[st].numL + 1;
a[nN].sumL = a[st].sumL + v;
}
return nN;
}
};
int dfs(int n, int p, int d, g_t &g, vector<int> &pa, vector<int> &de) {
de[n] = d;
int su = 1;
int ma = 0;
pa[n] = p;
for (auto &e: g[n]) {
if (e == p) continue;
int re = dfs(e, n, d + 1, g, pa, de);
su += re;
if (re > ma) {
swap(e, g[n][0]);
ma = re;
}
}
return su;
}
void segDfs(int n, int p, int seg, g_t &g, vector<PSegTe> &segs, vector<int> &segThis, g_t &cos) {
segThis[n] = seg;
if (seg == -1) {
segThis[n] = segs.size();
segs.push_back({{}, {}, n});
}
for (auto e: cos[n]) {
segs[segThis[n]].cooC.push_back(e);
}
bool first = true;
for (auto e: g[n]) {
if (e == p) continue;
if (first) {
segDfs(e, n, segThis[n], g, segs, segThis, cos);
first = false;
} else {
segDfs(e, n, -1, g, segs, segThis, cos);
}
}
}
void initSegDfs(int n, int p, int st, g_t &g, vector<PSegTe> &segs,
vector<int> &segThis, vector<int> &topSeg, g_t &cos) {
topSeg[n] = st;
for (auto e: cos[n]) {
topSeg[n] = segs[segThis[n]].add(topSeg[n], std::lower_bound(segs[segThis[n]].cooC.begin(),
segs[segThis[n]].cooC.end(), e) -
segs[segThis[n]].cooC.begin(), e);
}
bool first = true;
for (auto e: g[n]) {
if (e == p) continue;
if (first) {
initSegDfs(e, n, topSeg[n], g, segs, segThis, topSeg, cos);
first = false;
} else {
initSegDfs(e, n, 0, g, segs, segThis, topSeg, cos);
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int>> edge(n - 1);
g_t g(n);
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
--a; --b;
g[a].push_back(b);
g[b].push_back(a);
edge[i] = {a, b};
}
vector<int> p(n);
vector<int> d(n);
dfs(0, 0, 0, g, p, d);
for (int i = 0; i < n - 1; ++i) {
if (p[edge[i].first] != edge[i].second) swap(edge[i].first, edge[i].second);
}
g_t cos(n);
int cs = -1;
for (int i = 0; i < m; ++i) {
int pj, c;
cin >> pj >> c;
cs = c;
pj--;
cos[edge[pj].first].push_back(c);
}
vector<PSegTe> segs;
vector<int> segThis(n);
segDfs(0, 0, -1, g, segs, segThis, cos);
for (auto &seg: segs) {
std::sort(seg.cooC.begin(), seg.cooC.end());
seg.cooC.erase(std::unique(seg.cooC.begin(), seg.cooC.end()), seg.cooC.end());
seg.build(0, seg.cooC.size());
}
vector<int> topSeg(n);
initSegDfs(0, 0, 0, g, segs, segThis, topSeg, cos);
for (int i = 0; i < q; ++i) {
int a, b, gol, sil;
cin >> a >> b >> gol >> sil;
--a;
--b;
vector<SegAb> abs;
while (segThis[a] != segThis[b]) {
if (d[segs[segThis[a]].high] < d[segs[segThis[b]].high]) swap(a, b);
abs.push_back({a, -1, segThis[a]});
a = p[segs[segThis[a]].high];
}
if (d[a] < d[b]) swap(a, b);
if (a != b) {
abs.push_back({a, b, segThis[a]});
}
int numChe = 0;
for (auto &e: abs) {
numChe += segs[e.se].a[topSeg[e.st]].numL;
if (e.en != -1) {
numChe -= segs[e.se].a[topSeg[e.en]].numL;
}
}
int l = 0, r = 1e9 + 1;
while (l + 1 < r) {
m = (l + r) / 2;
int su = 0;
for (auto &e: abs) {
int k = std::upper_bound(segs[e.se].cooC.begin(), segs[e.se].cooC.end(), m) - segs[e.se].cooC.begin();
su += segs[e.se].get(topSeg[e.st], k).second;
if (e.en != -1) {
su -= segs[e.se].get(topSeg[e.en], k).second;
}
}
if (su >= sil) r = m;
else l = m;
}
int su = 0;
int nuS = 0;
for (auto &e: abs) {
int k = std::upper_bound(segs[e.se].cooC.begin(), segs[e.se].cooC.end(), r) - segs[e.se].cooC.begin();
auto res = segs[e.se].get(topSeg[e.st], k);
su += res.second;
nuS += res.first;
if (e.en != -1) {
res = segs[e.se].get(topSeg[e.en], k);
su -= res.second;
nuS -= res.first;
}
}
int dif = su - sil;
nuS -= (dif + r - 1)/r;
numChe -= nuS;
numChe = max(0ll, numChe);
if (gol - numChe < -1) numChe = gol + 1;
cout << gol - numChe << "\n";
}
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:148:6: warning: variable 'cs' set but not used [-Wunused-but-set-variable]
148 | int cs = -1;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
1368 KB |
Output is correct |
6 |
Correct |
8 ms |
1372 KB |
Output is correct |
7 |
Correct |
7 ms |
1112 KB |
Output is correct |
8 |
Correct |
9 ms |
1372 KB |
Output is correct |
9 |
Correct |
9 ms |
1368 KB |
Output is correct |
10 |
Correct |
9 ms |
1368 KB |
Output is correct |
11 |
Correct |
10 ms |
1372 KB |
Output is correct |
12 |
Correct |
9 ms |
1576 KB |
Output is correct |
13 |
Correct |
14 ms |
2772 KB |
Output is correct |
14 |
Correct |
15 ms |
3032 KB |
Output is correct |
15 |
Correct |
16 ms |
2320 KB |
Output is correct |
16 |
Correct |
15 ms |
2196 KB |
Output is correct |
17 |
Correct |
16 ms |
2192 KB |
Output is correct |
18 |
Correct |
16 ms |
2452 KB |
Output is correct |
19 |
Correct |
4 ms |
1368 KB |
Output is correct |
20 |
Correct |
4 ms |
1780 KB |
Output is correct |
21 |
Correct |
4 ms |
1368 KB |
Output is correct |
22 |
Correct |
4 ms |
1372 KB |
Output is correct |
23 |
Correct |
13 ms |
1940 KB |
Output is correct |
24 |
Correct |
11 ms |
1940 KB |
Output is correct |
25 |
Correct |
12 ms |
1940 KB |
Output is correct |
26 |
Correct |
7 ms |
1368 KB |
Output is correct |
27 |
Correct |
7 ms |
1368 KB |
Output is correct |
28 |
Correct |
8 ms |
1368 KB |
Output is correct |
29 |
Correct |
4 ms |
1368 KB |
Output is correct |
30 |
Correct |
5 ms |
1112 KB |
Output is correct |
31 |
Correct |
5 ms |
1112 KB |
Output is correct |
32 |
Correct |
5 ms |
1116 KB |
Output is correct |
33 |
Correct |
14 ms |
2780 KB |
Output is correct |
34 |
Correct |
14 ms |
2780 KB |
Output is correct |
35 |
Correct |
13 ms |
2784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
1116 KB |
Output is correct |
3 |
Correct |
5 ms |
1112 KB |
Output is correct |
4 |
Correct |
5 ms |
1116 KB |
Output is correct |
5 |
Correct |
262 ms |
33600 KB |
Output is correct |
6 |
Correct |
287 ms |
26644 KB |
Output is correct |
7 |
Correct |
283 ms |
28068 KB |
Output is correct |
8 |
Correct |
228 ms |
28916 KB |
Output is correct |
9 |
Correct |
221 ms |
29180 KB |
Output is correct |
10 |
Correct |
352 ms |
35572 KB |
Output is correct |
11 |
Correct |
335 ms |
35116 KB |
Output is correct |
12 |
Correct |
331 ms |
35820 KB |
Output is correct |
13 |
Correct |
366 ms |
35352 KB |
Output is correct |
14 |
Correct |
336 ms |
35588 KB |
Output is correct |
15 |
Correct |
183 ms |
45428 KB |
Output is correct |
16 |
Correct |
186 ms |
46772 KB |
Output is correct |
17 |
Correct |
188 ms |
45492 KB |
Output is correct |
18 |
Correct |
227 ms |
28792 KB |
Output is correct |
19 |
Correct |
240 ms |
28492 KB |
Output is correct |
20 |
Correct |
227 ms |
28752 KB |
Output is correct |
21 |
Correct |
212 ms |
42804 KB |
Output is correct |
22 |
Correct |
207 ms |
41640 KB |
Output is correct |
23 |
Correct |
228 ms |
41780 KB |
Output is correct |
24 |
Correct |
212 ms |
41380 KB |
Output is correct |
25 |
Correct |
321 ms |
36596 KB |
Output is correct |
26 |
Correct |
351 ms |
36012 KB |
Output is correct |
27 |
Correct |
346 ms |
36728 KB |
Output is correct |
28 |
Correct |
279 ms |
35024 KB |
Output is correct |
29 |
Correct |
271 ms |
35240 KB |
Output is correct |
30 |
Correct |
316 ms |
35852 KB |
Output is correct |
31 |
Correct |
301 ms |
35412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
13 ms |
3036 KB |
Output is correct |
3 |
Correct |
13 ms |
2780 KB |
Output is correct |
4 |
Correct |
13 ms |
2780 KB |
Output is correct |
5 |
Correct |
1311 ms |
134420 KB |
Output is correct |
6 |
Correct |
1153 ms |
82540 KB |
Output is correct |
7 |
Correct |
1996 ms |
121680 KB |
Output is correct |
8 |
Correct |
2715 ms |
137628 KB |
Output is correct |
9 |
Correct |
2690 ms |
137252 KB |
Output is correct |
10 |
Correct |
2675 ms |
136348 KB |
Output is correct |
11 |
Correct |
2136 ms |
136852 KB |
Output is correct |
12 |
Correct |
2122 ms |
136736 KB |
Output is correct |
13 |
Correct |
2079 ms |
135968 KB |
Output is correct |
14 |
Correct |
1332 ms |
137760 KB |
Output is correct |
15 |
Correct |
1309 ms |
136348 KB |
Output is correct |
16 |
Correct |
1594 ms |
137880 KB |
Output is correct |
17 |
Correct |
1554 ms |
137628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
6 ms |
1368 KB |
Output is correct |
6 |
Correct |
8 ms |
1372 KB |
Output is correct |
7 |
Correct |
7 ms |
1112 KB |
Output is correct |
8 |
Correct |
9 ms |
1372 KB |
Output is correct |
9 |
Correct |
9 ms |
1368 KB |
Output is correct |
10 |
Correct |
9 ms |
1368 KB |
Output is correct |
11 |
Correct |
10 ms |
1372 KB |
Output is correct |
12 |
Correct |
9 ms |
1576 KB |
Output is correct |
13 |
Correct |
14 ms |
2772 KB |
Output is correct |
14 |
Correct |
15 ms |
3032 KB |
Output is correct |
15 |
Correct |
16 ms |
2320 KB |
Output is correct |
16 |
Correct |
15 ms |
2196 KB |
Output is correct |
17 |
Correct |
16 ms |
2192 KB |
Output is correct |
18 |
Correct |
16 ms |
2452 KB |
Output is correct |
19 |
Correct |
4 ms |
1368 KB |
Output is correct |
20 |
Correct |
4 ms |
1780 KB |
Output is correct |
21 |
Correct |
4 ms |
1368 KB |
Output is correct |
22 |
Correct |
4 ms |
1372 KB |
Output is correct |
23 |
Correct |
13 ms |
1940 KB |
Output is correct |
24 |
Correct |
11 ms |
1940 KB |
Output is correct |
25 |
Correct |
12 ms |
1940 KB |
Output is correct |
26 |
Correct |
7 ms |
1368 KB |
Output is correct |
27 |
Correct |
7 ms |
1368 KB |
Output is correct |
28 |
Correct |
8 ms |
1368 KB |
Output is correct |
29 |
Correct |
4 ms |
1368 KB |
Output is correct |
30 |
Correct |
5 ms |
1112 KB |
Output is correct |
31 |
Correct |
5 ms |
1112 KB |
Output is correct |
32 |
Correct |
5 ms |
1116 KB |
Output is correct |
33 |
Correct |
14 ms |
2780 KB |
Output is correct |
34 |
Correct |
14 ms |
2780 KB |
Output is correct |
35 |
Correct |
13 ms |
2784 KB |
Output is correct |
36 |
Correct |
0 ms |
344 KB |
Output is correct |
37 |
Correct |
5 ms |
1116 KB |
Output is correct |
38 |
Correct |
5 ms |
1112 KB |
Output is correct |
39 |
Correct |
5 ms |
1116 KB |
Output is correct |
40 |
Correct |
262 ms |
33600 KB |
Output is correct |
41 |
Correct |
287 ms |
26644 KB |
Output is correct |
42 |
Correct |
283 ms |
28068 KB |
Output is correct |
43 |
Correct |
228 ms |
28916 KB |
Output is correct |
44 |
Correct |
221 ms |
29180 KB |
Output is correct |
45 |
Correct |
352 ms |
35572 KB |
Output is correct |
46 |
Correct |
335 ms |
35116 KB |
Output is correct |
47 |
Correct |
331 ms |
35820 KB |
Output is correct |
48 |
Correct |
366 ms |
35352 KB |
Output is correct |
49 |
Correct |
336 ms |
35588 KB |
Output is correct |
50 |
Correct |
183 ms |
45428 KB |
Output is correct |
51 |
Correct |
186 ms |
46772 KB |
Output is correct |
52 |
Correct |
188 ms |
45492 KB |
Output is correct |
53 |
Correct |
227 ms |
28792 KB |
Output is correct |
54 |
Correct |
240 ms |
28492 KB |
Output is correct |
55 |
Correct |
227 ms |
28752 KB |
Output is correct |
56 |
Correct |
212 ms |
42804 KB |
Output is correct |
57 |
Correct |
207 ms |
41640 KB |
Output is correct |
58 |
Correct |
228 ms |
41780 KB |
Output is correct |
59 |
Correct |
212 ms |
41380 KB |
Output is correct |
60 |
Correct |
321 ms |
36596 KB |
Output is correct |
61 |
Correct |
351 ms |
36012 KB |
Output is correct |
62 |
Correct |
346 ms |
36728 KB |
Output is correct |
63 |
Correct |
279 ms |
35024 KB |
Output is correct |
64 |
Correct |
271 ms |
35240 KB |
Output is correct |
65 |
Correct |
316 ms |
35852 KB |
Output is correct |
66 |
Correct |
301 ms |
35412 KB |
Output is correct |
67 |
Correct |
0 ms |
344 KB |
Output is correct |
68 |
Correct |
13 ms |
3036 KB |
Output is correct |
69 |
Correct |
13 ms |
2780 KB |
Output is correct |
70 |
Correct |
13 ms |
2780 KB |
Output is correct |
71 |
Correct |
1311 ms |
134420 KB |
Output is correct |
72 |
Correct |
1153 ms |
82540 KB |
Output is correct |
73 |
Correct |
1996 ms |
121680 KB |
Output is correct |
74 |
Correct |
2715 ms |
137628 KB |
Output is correct |
75 |
Correct |
2690 ms |
137252 KB |
Output is correct |
76 |
Correct |
2675 ms |
136348 KB |
Output is correct |
77 |
Correct |
2136 ms |
136852 KB |
Output is correct |
78 |
Correct |
2122 ms |
136736 KB |
Output is correct |
79 |
Correct |
2079 ms |
135968 KB |
Output is correct |
80 |
Correct |
1332 ms |
137760 KB |
Output is correct |
81 |
Correct |
1309 ms |
136348 KB |
Output is correct |
82 |
Correct |
1594 ms |
137880 KB |
Output is correct |
83 |
Correct |
1554 ms |
137628 KB |
Output is correct |
84 |
Correct |
538 ms |
51672 KB |
Output is correct |
85 |
Correct |
625 ms |
46876 KB |
Output is correct |
86 |
Correct |
528 ms |
33804 KB |
Output is correct |
87 |
Correct |
830 ms |
56564 KB |
Output is correct |
88 |
Correct |
885 ms |
56676 KB |
Output is correct |
89 |
Correct |
883 ms |
57080 KB |
Output is correct |
90 |
Correct |
858 ms |
56332 KB |
Output is correct |
91 |
Correct |
870 ms |
57116 KB |
Output is correct |
92 |
Correct |
2992 ms |
160948 KB |
Output is correct |
93 |
Correct |
2923 ms |
153612 KB |
Output is correct |
94 |
Correct |
2413 ms |
84160 KB |
Output is correct |
95 |
Correct |
2425 ms |
84676 KB |
Output is correct |
96 |
Correct |
2397 ms |
83892 KB |
Output is correct |
97 |
Correct |
2521 ms |
83364 KB |
Output is correct |
98 |
Correct |
264 ms |
53160 KB |
Output is correct |
99 |
Correct |
248 ms |
51248 KB |
Output is correct |
100 |
Correct |
257 ms |
52376 KB |
Output is correct |
101 |
Correct |
255 ms |
53048 KB |
Output is correct |
102 |
Correct |
1022 ms |
83360 KB |
Output is correct |
103 |
Correct |
1220 ms |
83800 KB |
Output is correct |
104 |
Correct |
1189 ms |
84712 KB |
Output is correct |
105 |
Correct |
590 ms |
56576 KB |
Output is correct |
106 |
Correct |
555 ms |
56284 KB |
Output is correct |
107 |
Correct |
545 ms |
56320 KB |
Output is correct |
108 |
Correct |
638 ms |
56320 KB |
Output is correct |