//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007, LOG = 20;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
struct BIT {
vector<ll> tree;
BIT(ll n) {
tree.resize(n + 1, 0);
}
ll get(ll x) {
ll ans = 0;
for (; x > 0; x -= x & -x) {
ans += tree[x];
}
return ans;
}
void add(ll x, ll y) {
x++;
for (; x < tree.size(); x += x & -x) {
tree[x] += y;
}
}
void clear() {
for (auto& i : tree) {
i = 0;
}
}
};
struct LCA {
vector<vector<ll>> binup;
vector<ll> h;
LCA(vector<vector<ll>>& tree) {
binup.resize(LOG, vector<ll>(tree.size(), 0));
h.resize(tree.size(), -1);
dfs(0, 0, tree);
}
void dfs(ll v, ll p, vector<vector<ll>>& tree) {
h[v] = h[p] + 1;
binup[0][v] = p;
for (ll i = 1; i < LOG; i++) {
binup[i][v] = binup[i - 1][binup[i - 1][v]];
}
for (auto i : tree[v]) {
if (i != p) {
dfs(i, v, tree);
}
}
}
ll get_LA(ll v, ll x) {
for (ll i = 0; i < LOG; i++) {
if ((x >> i) & 1) {
x -= 1 << i;
v = binup[i][v];
}
}
return v;
}
ll get(ll a, ll b) {
if (h[a] < h[b]) {
swap(a, b);
}
a = get_LA(a, h[a] - h[b]);
if (a == b) {
return a;
}
for (ll i = LOG - 1; i >= 0; i--) {
if (binup[i][a] != binup[i][b]) {
a = binup[i][a];
b = binup[i][b];
}
}
return binup[0][a];
}
};
void dfs(ll v, ll p, vector<vector<ll>>& tree, BIT& bi, BIT& bc, vector<vector<pair<ll, ll>>>& cs, vector<vector<pair<ll, ll>>>& qs, vector<pair<ll, ll>>& ans, ll nc) {
for (auto[a, b] : cs[v]) {
bi.add(a, b);
bc.add(a, 1);
nc++;
}
for (auto i : tree[v]) {
if (i != p) {
dfs(i, v, tree, bi, bc, cs, qs, ans, nc);
}
}
for (auto[a, b] : qs[v]) {
ans[b].first = bi.get(a);
ans[b].second = nc - bc.get(a);
}
for (auto[a, b] : cs[v]) {
bi.add(a, -b);
bc.add(a, -1);
}
}
void solve() {
ll n, m, q;
cin >> n >> m >> q;
vector<vector<ll>> tree(n);
vector<pair<ll, ll>> rs;
for (ll i = 1; i < n; i++) {
ll a, b;
cin >> a >> b;
a--;
b--;
rs.emplace_back(a, b);
tree[a].push_back(b);
tree[b].push_back(a);
}
LCA l(tree);
vector<ll> pred;
for (auto[a, b] : rs) {
pred.push_back((l.get(a, b) == a ? b : a));
}
vector<vector<pair<ll, ll>>> cs(n);
vector<pair<ll, ll>> all;
for (ll i = 0; i < m; i++) {
ll p, c;
cin >> p >> c;
p--;
p = pred[p];
all.emplace_back(c, p);
}
sort(all.begin(), all.end());
for (ll i = 0; i < m; i++) {
cs[all[i].second].push_back(make_pair(i, all[i].first));
}
vector<tuple<ll, ll, ll, ll, ll, ll, ll>> qs;
vector<ll> ans;
for (ll i = 0; i < q; i++) {
ll s, t, x, y;
cin >> s >> t >> x >> y;
s--;
t--;
qs.emplace_back(0, m + 1, s, t, l.get(s, t), y, x);
ans.push_back(x + 1);
}
for (ll _ = 0; _ < LOG; _++) {
vector<vector<pair<ll, ll>>> nqs(n);
vector<pair<ll, ll>> anss(q * 3);
BIT bi(m), bc(m);
for (ll i = 0; i < q; i++) {
auto[l, r, s, t, lca, y, x] = qs[i];
ll mid = (l + r) / 2;
nqs[s].emplace_back(mid, i * 3);
nqs[t].emplace_back(mid, i * 3 + 1);
nqs[lca].emplace_back(mid, i * 3 + 2);
}
dfs(0, 0, tree, bi, bc, cs, nqs, anss, 0);
for (ll i = 0; i < q; i++) {
ll na = anss[i * 3].first + anss[i * 3 + 1].first - anss[i * 3 + 2].first * 2;
auto&[l, r, s, t, lca, y, x] = qs[i];
ll mid = (l + r) / 2;
if (na > y) {
r = mid;
} else {
l = mid;
assign_min(ans[i], anss[i * 3].second + anss[i * 3 + 1].second - anss[i * 3 + 2].second * 2);
}
}
}
for (ll i = 0; i < q; i++) {
cout << get<6>(qs[i]) - ans[i] << '\n';
}
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}
Compilation message
currencies.cpp: In member function 'void BIT::add(ll, ll)':
currencies.cpp:64:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (; x < tree.size(); x += x & -x) {
| ~~^~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:216:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
216 | freopen("", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~
currencies.cpp:217:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
217 | freopen("", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
9 ms |
1432 KB |
Output is correct |
6 |
Correct |
15 ms |
1860 KB |
Output is correct |
7 |
Correct |
9 ms |
1372 KB |
Output is correct |
8 |
Correct |
12 ms |
1552 KB |
Output is correct |
9 |
Correct |
12 ms |
1416 KB |
Output is correct |
10 |
Correct |
16 ms |
1508 KB |
Output is correct |
11 |
Correct |
12 ms |
1628 KB |
Output is correct |
12 |
Correct |
12 ms |
1628 KB |
Output is correct |
13 |
Correct |
13 ms |
1628 KB |
Output is correct |
14 |
Correct |
13 ms |
1792 KB |
Output is correct |
15 |
Correct |
13 ms |
1628 KB |
Output is correct |
16 |
Correct |
12 ms |
1624 KB |
Output is correct |
17 |
Correct |
13 ms |
1536 KB |
Output is correct |
18 |
Correct |
13 ms |
1472 KB |
Output is correct |
19 |
Correct |
10 ms |
1468 KB |
Output is correct |
20 |
Correct |
12 ms |
1628 KB |
Output is correct |
21 |
Correct |
11 ms |
1628 KB |
Output is correct |
22 |
Correct |
11 ms |
1624 KB |
Output is correct |
23 |
Correct |
10 ms |
1628 KB |
Output is correct |
24 |
Correct |
10 ms |
1444 KB |
Output is correct |
25 |
Correct |
10 ms |
1624 KB |
Output is correct |
26 |
Correct |
8 ms |
1628 KB |
Output is correct |
27 |
Correct |
8 ms |
1628 KB |
Output is correct |
28 |
Correct |
9 ms |
1628 KB |
Output is correct |
29 |
Correct |
8 ms |
1616 KB |
Output is correct |
30 |
Correct |
15 ms |
1628 KB |
Output is correct |
31 |
Correct |
12 ms |
1628 KB |
Output is correct |
32 |
Correct |
17 ms |
1628 KB |
Output is correct |
33 |
Correct |
12 ms |
1880 KB |
Output is correct |
34 |
Correct |
12 ms |
1884 KB |
Output is correct |
35 |
Correct |
13 ms |
1880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
464 KB |
Output is correct |
2 |
Correct |
12 ms |
1628 KB |
Output is correct |
3 |
Correct |
12 ms |
1628 KB |
Output is correct |
4 |
Correct |
12 ms |
1664 KB |
Output is correct |
5 |
Correct |
1289 ms |
51612 KB |
Output is correct |
6 |
Correct |
1225 ms |
50240 KB |
Output is correct |
7 |
Correct |
1433 ms |
52260 KB |
Output is correct |
8 |
Correct |
1174 ms |
46620 KB |
Output is correct |
9 |
Correct |
1195 ms |
46004 KB |
Output is correct |
10 |
Correct |
1811 ms |
60324 KB |
Output is correct |
11 |
Correct |
1789 ms |
61084 KB |
Output is correct |
12 |
Correct |
1833 ms |
60700 KB |
Output is correct |
13 |
Correct |
1810 ms |
60580 KB |
Output is correct |
14 |
Correct |
1777 ms |
60092 KB |
Output is correct |
15 |
Correct |
2251 ms |
71336 KB |
Output is correct |
16 |
Correct |
2263 ms |
72988 KB |
Output is correct |
17 |
Correct |
2181 ms |
71256 KB |
Output is correct |
18 |
Correct |
2138 ms |
60772 KB |
Output is correct |
19 |
Correct |
1997 ms |
60088 KB |
Output is correct |
20 |
Correct |
2047 ms |
60572 KB |
Output is correct |
21 |
Correct |
1487 ms |
60460 KB |
Output is correct |
22 |
Correct |
1536 ms |
61840 KB |
Output is correct |
23 |
Correct |
1427 ms |
60524 KB |
Output is correct |
24 |
Correct |
1541 ms |
62056 KB |
Output is correct |
25 |
Correct |
1190 ms |
62468 KB |
Output is correct |
26 |
Correct |
1211 ms |
62604 KB |
Output is correct |
27 |
Correct |
1213 ms |
63088 KB |
Output is correct |
28 |
Correct |
1098 ms |
60540 KB |
Output is correct |
29 |
Correct |
1039 ms |
60112 KB |
Output is correct |
30 |
Correct |
1191 ms |
61496 KB |
Output is correct |
31 |
Correct |
1149 ms |
62332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
13 ms |
1732 KB |
Output is correct |
3 |
Correct |
11 ms |
1884 KB |
Output is correct |
4 |
Correct |
13 ms |
1756 KB |
Output is correct |
5 |
Correct |
900 ms |
60160 KB |
Output is correct |
6 |
Correct |
821 ms |
59736 KB |
Output is correct |
7 |
Correct |
1004 ms |
51036 KB |
Output is correct |
8 |
Correct |
1423 ms |
73184 KB |
Output is correct |
9 |
Correct |
1431 ms |
72316 KB |
Output is correct |
10 |
Correct |
1381 ms |
72904 KB |
Output is correct |
11 |
Correct |
1010 ms |
75180 KB |
Output is correct |
12 |
Correct |
976 ms |
71788 KB |
Output is correct |
13 |
Correct |
1012 ms |
72676 KB |
Output is correct |
14 |
Correct |
751 ms |
74488 KB |
Output is correct |
15 |
Correct |
817 ms |
74892 KB |
Output is correct |
16 |
Correct |
910 ms |
75028 KB |
Output is correct |
17 |
Correct |
896 ms |
78720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
9 ms |
1432 KB |
Output is correct |
6 |
Correct |
15 ms |
1860 KB |
Output is correct |
7 |
Correct |
9 ms |
1372 KB |
Output is correct |
8 |
Correct |
12 ms |
1552 KB |
Output is correct |
9 |
Correct |
12 ms |
1416 KB |
Output is correct |
10 |
Correct |
16 ms |
1508 KB |
Output is correct |
11 |
Correct |
12 ms |
1628 KB |
Output is correct |
12 |
Correct |
12 ms |
1628 KB |
Output is correct |
13 |
Correct |
13 ms |
1628 KB |
Output is correct |
14 |
Correct |
13 ms |
1792 KB |
Output is correct |
15 |
Correct |
13 ms |
1628 KB |
Output is correct |
16 |
Correct |
12 ms |
1624 KB |
Output is correct |
17 |
Correct |
13 ms |
1536 KB |
Output is correct |
18 |
Correct |
13 ms |
1472 KB |
Output is correct |
19 |
Correct |
10 ms |
1468 KB |
Output is correct |
20 |
Correct |
12 ms |
1628 KB |
Output is correct |
21 |
Correct |
11 ms |
1628 KB |
Output is correct |
22 |
Correct |
11 ms |
1624 KB |
Output is correct |
23 |
Correct |
10 ms |
1628 KB |
Output is correct |
24 |
Correct |
10 ms |
1444 KB |
Output is correct |
25 |
Correct |
10 ms |
1624 KB |
Output is correct |
26 |
Correct |
8 ms |
1628 KB |
Output is correct |
27 |
Correct |
8 ms |
1628 KB |
Output is correct |
28 |
Correct |
9 ms |
1628 KB |
Output is correct |
29 |
Correct |
8 ms |
1616 KB |
Output is correct |
30 |
Correct |
15 ms |
1628 KB |
Output is correct |
31 |
Correct |
12 ms |
1628 KB |
Output is correct |
32 |
Correct |
17 ms |
1628 KB |
Output is correct |
33 |
Correct |
12 ms |
1880 KB |
Output is correct |
34 |
Correct |
12 ms |
1884 KB |
Output is correct |
35 |
Correct |
13 ms |
1880 KB |
Output is correct |
36 |
Correct |
1 ms |
464 KB |
Output is correct |
37 |
Correct |
12 ms |
1628 KB |
Output is correct |
38 |
Correct |
12 ms |
1628 KB |
Output is correct |
39 |
Correct |
12 ms |
1664 KB |
Output is correct |
40 |
Correct |
1289 ms |
51612 KB |
Output is correct |
41 |
Correct |
1225 ms |
50240 KB |
Output is correct |
42 |
Correct |
1433 ms |
52260 KB |
Output is correct |
43 |
Correct |
1174 ms |
46620 KB |
Output is correct |
44 |
Correct |
1195 ms |
46004 KB |
Output is correct |
45 |
Correct |
1811 ms |
60324 KB |
Output is correct |
46 |
Correct |
1789 ms |
61084 KB |
Output is correct |
47 |
Correct |
1833 ms |
60700 KB |
Output is correct |
48 |
Correct |
1810 ms |
60580 KB |
Output is correct |
49 |
Correct |
1777 ms |
60092 KB |
Output is correct |
50 |
Correct |
2251 ms |
71336 KB |
Output is correct |
51 |
Correct |
2263 ms |
72988 KB |
Output is correct |
52 |
Correct |
2181 ms |
71256 KB |
Output is correct |
53 |
Correct |
2138 ms |
60772 KB |
Output is correct |
54 |
Correct |
1997 ms |
60088 KB |
Output is correct |
55 |
Correct |
2047 ms |
60572 KB |
Output is correct |
56 |
Correct |
1487 ms |
60460 KB |
Output is correct |
57 |
Correct |
1536 ms |
61840 KB |
Output is correct |
58 |
Correct |
1427 ms |
60524 KB |
Output is correct |
59 |
Correct |
1541 ms |
62056 KB |
Output is correct |
60 |
Correct |
1190 ms |
62468 KB |
Output is correct |
61 |
Correct |
1211 ms |
62604 KB |
Output is correct |
62 |
Correct |
1213 ms |
63088 KB |
Output is correct |
63 |
Correct |
1098 ms |
60540 KB |
Output is correct |
64 |
Correct |
1039 ms |
60112 KB |
Output is correct |
65 |
Correct |
1191 ms |
61496 KB |
Output is correct |
66 |
Correct |
1149 ms |
62332 KB |
Output is correct |
67 |
Correct |
1 ms |
344 KB |
Output is correct |
68 |
Correct |
13 ms |
1732 KB |
Output is correct |
69 |
Correct |
11 ms |
1884 KB |
Output is correct |
70 |
Correct |
13 ms |
1756 KB |
Output is correct |
71 |
Correct |
900 ms |
60160 KB |
Output is correct |
72 |
Correct |
821 ms |
59736 KB |
Output is correct |
73 |
Correct |
1004 ms |
51036 KB |
Output is correct |
74 |
Correct |
1423 ms |
73184 KB |
Output is correct |
75 |
Correct |
1431 ms |
72316 KB |
Output is correct |
76 |
Correct |
1381 ms |
72904 KB |
Output is correct |
77 |
Correct |
1010 ms |
75180 KB |
Output is correct |
78 |
Correct |
976 ms |
71788 KB |
Output is correct |
79 |
Correct |
1012 ms |
72676 KB |
Output is correct |
80 |
Correct |
751 ms |
74488 KB |
Output is correct |
81 |
Correct |
817 ms |
74892 KB |
Output is correct |
82 |
Correct |
910 ms |
75028 KB |
Output is correct |
83 |
Correct |
896 ms |
78720 KB |
Output is correct |
84 |
Correct |
1339 ms |
46656 KB |
Output is correct |
85 |
Correct |
1037 ms |
41144 KB |
Output is correct |
86 |
Correct |
922 ms |
39976 KB |
Output is correct |
87 |
Correct |
1837 ms |
61180 KB |
Output is correct |
88 |
Correct |
1798 ms |
60124 KB |
Output is correct |
89 |
Correct |
1791 ms |
60052 KB |
Output is correct |
90 |
Correct |
1858 ms |
60204 KB |
Output is correct |
91 |
Correct |
1827 ms |
60232 KB |
Output is correct |
92 |
Correct |
2277 ms |
68200 KB |
Output is correct |
93 |
Correct |
2288 ms |
71168 KB |
Output is correct |
94 |
Correct |
2081 ms |
60248 KB |
Output is correct |
95 |
Correct |
1978 ms |
59508 KB |
Output is correct |
96 |
Correct |
2003 ms |
60144 KB |
Output is correct |
97 |
Correct |
1986 ms |
61004 KB |
Output is correct |
98 |
Correct |
1456 ms |
61040 KB |
Output is correct |
99 |
Correct |
1432 ms |
60416 KB |
Output is correct |
100 |
Correct |
1419 ms |
61984 KB |
Output is correct |
101 |
Correct |
1393 ms |
62172 KB |
Output is correct |
102 |
Correct |
1192 ms |
60244 KB |
Output is correct |
103 |
Correct |
1163 ms |
59872 KB |
Output is correct |
104 |
Correct |
1128 ms |
61796 KB |
Output is correct |
105 |
Correct |
1076 ms |
60328 KB |
Output is correct |
106 |
Correct |
1051 ms |
62220 KB |
Output is correct |
107 |
Correct |
1079 ms |
64100 KB |
Output is correct |
108 |
Correct |
1139 ms |
64468 KB |
Output is correct |