#include <bits/stdc++.h>
using namespace std;
using p = pair<int, int>;
const int MAX_N = 100105;
int n, m, q, id=1, len=131072, ids[MAX_N], sz[MAX_N], depth[MAX_N] = {0};
long long tree[262144];
vector<int> paths[MAX_N];
vector<p> pathsA;
int table[18][MAX_N];
int LCA(int a, int b) {
if(depth[a] != depth[b]) {
if(depth[a] < depth[b]) swap(a, b);
int diff = depth[a] - depth[b];
for(int i = 17; i >= 0; i --) {
if(diff & (1 << i)) {
a = table[i][a];
}
}
}
assert(depth[a] == depth[b]);
for(int i = 17; i >= 0; i --) {
if(table[i][a] != table[i][b]) {
a = table[i][a];
b = table[i][b];
}
}
if(a != b) a = table[0][a];
return a;
}
void calcTable() {
for(int i = 1; i < 18; i ++) {
for(int j = 1; j <= n; j ++) {
table[i][j] = table[i - 1][table[i - 1][j]];
}
}
}
void dfs(int cur=1, int prev=-1) {
ids[cur] = id ++;
sz[cur] = 1;
for(int i: paths[cur]) {
if(i == prev) continue;
table[0][i] = cur;
depth[i] = depth[cur] + 1;
dfs(i, cur);
sz[cur] += sz[i];
}
}
void update(int a, int v) {
a += len;
tree[a] += (long long)v;
for(a /= 2; a >= 1; a /= 2) {
tree[a] = tree[a * 2] + tree[a * 2 + 1];
}
}
void rangeUpdate(int a, int v) {
int b = ids[a] + sz[a];
// if(ids[a] <= 10) assert(b >= 1863);
a = ids[a];
update(a, v);
update(b, -v);
}
long long query(int a, int b) {
a += len;
b += len;
long long tot = 0;
for(; a <= b; a /= 2, b /= 2) {
if(a & 1) {
tot += tree[a ++];
}
if(!(b & 1)) {
tot += tree[b --];
}
}
return tot;
}
long long query(int b) {
int a = 0;
b = ids[b];
return query(a, b);
}
vector<p> sts, lh;
vector<int> ans, cnts, mids[MAX_N];
struct N {
int a, b, c;
long long g, s;
N() {}
};
vector<N> qs;
int main() {
// cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for(int i = 1; i < n; i ++) {
int a, b;
cin >> a >> b;
paths[a].push_back(b);
paths[b].push_back(a);
pathsA.push_back({a, b});
}
dfs(); calcTable();
sts.resize(m);
for(int i = 0; i < m; i ++) {
cin >> sts[i].second >> sts[i].first;
sts[i].second --;
sts[i].second = depth[pathsA[sts[i].second].first] > depth[pathsA[sts[i].second].second] ? pathsA[sts[i].second].first : pathsA[sts[i].second].second;
}
sort(sts.begin(), sts.end());
qs.resize(q); ans.resize(q); lh.resize(q); cnts.resize(q);
for(int i = 0; i < q; i ++) {
cin >> qs[i].a >> qs[i].b >> qs[i].g >> qs[i].s;
qs[i].c = LCA(qs[i].a, qs[i].b);
lh[i] = {0, m - 1};
ans[i] = -1;
}
while(1) {
bool emp = true;
for(int i = 0; i < q; i ++) {
auto&[low, high] = lh[i];
if(low > high) continue;
emp = false;
mids[(low + high) >> 1].push_back(i);
}
for(auto&i: tree) i = 0;
for(int l = 0; l < m; l ++) {
auto&[C, P] = sts[l];
rangeUpdate(P, (emp ? 1 : C));
for(auto i: mids[l]) {
N& q = qs[i];
long long cs = query(q.a) + query(q.b) - query(q.c) * 2LL;
if(cs < 0) {
cout << query(q.a) << " " << query(q.b) << " " << query(q.c) << "\n";
cout << depth[q.a] << " " << depth[q.b] << " " << depth[q.c] << "\n";
cout << ids[q.a] << " " << ids[q.b] << " " << ids[q.c] << "\n";
cout << cs << "\n";
assert(0 != 0);
}
assert(cs >= 0);
auto&[low, high] = lh[i];
if(cs <= q.s) {
ans[i] = l;
low = l + 1;
} else {
high = l - 1;
}
}
mids[l].clear();
}
if(emp) {
for(int i = 0; i < q; i ++) {
N& q = qs[i];
cnts[i] = (int)(query(q.a) + query(q.b) - query(q.c) * 2);
if(ans[i] >= 0) mids[ans[i]].push_back(i);
}
for(auto&i: tree) i = 0;
break;
}
}
for(int l = 0; l < m; l ++) {
auto&[C, P] = sts[l];
rangeUpdate(P, 1);
for(auto i: mids[l]) {
N& q = qs[i];
int cs = (int)(query(q.a) + query(q.b) - query(q.c) * 2);
cnts[i] -= cs;
}
}
for(int i = 0; i < q; i ++) {
if(cnts[i] <= qs[i].g) cout << qs[i].g - cnts[i] << "\n";
else cout << "-1\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14936 KB |
Output is correct |
3 |
Correct |
3 ms |
14936 KB |
Output is correct |
4 |
Correct |
3 ms |
14936 KB |
Output is correct |
5 |
Correct |
10 ms |
15200 KB |
Output is correct |
6 |
Correct |
12 ms |
15192 KB |
Output is correct |
7 |
Correct |
10 ms |
15192 KB |
Output is correct |
8 |
Correct |
12 ms |
15192 KB |
Output is correct |
9 |
Correct |
12 ms |
15192 KB |
Output is correct |
10 |
Correct |
12 ms |
15192 KB |
Output is correct |
11 |
Correct |
13 ms |
15192 KB |
Output is correct |
12 |
Correct |
12 ms |
15192 KB |
Output is correct |
13 |
Correct |
16 ms |
15448 KB |
Output is correct |
14 |
Correct |
13 ms |
15448 KB |
Output is correct |
15 |
Correct |
13 ms |
15452 KB |
Output is correct |
16 |
Correct |
13 ms |
15448 KB |
Output is correct |
17 |
Correct |
13 ms |
15448 KB |
Output is correct |
18 |
Correct |
13 ms |
15448 KB |
Output is correct |
19 |
Correct |
14 ms |
15440 KB |
Output is correct |
20 |
Correct |
11 ms |
15192 KB |
Output is correct |
21 |
Correct |
11 ms |
15196 KB |
Output is correct |
22 |
Correct |
12 ms |
15192 KB |
Output is correct |
23 |
Correct |
11 ms |
15192 KB |
Output is correct |
24 |
Correct |
11 ms |
15192 KB |
Output is correct |
25 |
Correct |
11 ms |
15396 KB |
Output is correct |
26 |
Correct |
10 ms |
15192 KB |
Output is correct |
27 |
Correct |
9 ms |
15236 KB |
Output is correct |
28 |
Correct |
10 ms |
15192 KB |
Output is correct |
29 |
Correct |
9 ms |
15236 KB |
Output is correct |
30 |
Correct |
12 ms |
15192 KB |
Output is correct |
31 |
Correct |
12 ms |
15192 KB |
Output is correct |
32 |
Correct |
14 ms |
15192 KB |
Output is correct |
33 |
Correct |
13 ms |
15448 KB |
Output is correct |
34 |
Correct |
13 ms |
15448 KB |
Output is correct |
35 |
Correct |
14 ms |
15448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14764 KB |
Output is correct |
2 |
Correct |
12 ms |
15192 KB |
Output is correct |
3 |
Correct |
15 ms |
15192 KB |
Output is correct |
4 |
Correct |
15 ms |
15192 KB |
Output is correct |
5 |
Correct |
576 ms |
33364 KB |
Output is correct |
6 |
Correct |
765 ms |
37340 KB |
Output is correct |
7 |
Correct |
703 ms |
36804 KB |
Output is correct |
8 |
Correct |
557 ms |
32704 KB |
Output is correct |
9 |
Correct |
534 ms |
32260 KB |
Output is correct |
10 |
Correct |
873 ms |
40304 KB |
Output is correct |
11 |
Correct |
854 ms |
40432 KB |
Output is correct |
12 |
Correct |
927 ms |
40128 KB |
Output is correct |
13 |
Correct |
907 ms |
40128 KB |
Output is correct |
14 |
Correct |
825 ms |
40320 KB |
Output is correct |
15 |
Correct |
956 ms |
48056 KB |
Output is correct |
16 |
Correct |
1008 ms |
48728 KB |
Output is correct |
17 |
Correct |
941 ms |
47812 KB |
Output is correct |
18 |
Correct |
883 ms |
40644 KB |
Output is correct |
19 |
Correct |
904 ms |
40828 KB |
Output is correct |
20 |
Correct |
946 ms |
40900 KB |
Output is correct |
21 |
Correct |
794 ms |
40596 KB |
Output is correct |
22 |
Correct |
789 ms |
40672 KB |
Output is correct |
23 |
Correct |
748 ms |
40456 KB |
Output is correct |
24 |
Correct |
748 ms |
40588 KB |
Output is correct |
25 |
Correct |
764 ms |
40100 KB |
Output is correct |
26 |
Correct |
695 ms |
40148 KB |
Output is correct |
27 |
Correct |
661 ms |
40436 KB |
Output is correct |
28 |
Correct |
478 ms |
38956 KB |
Output is correct |
29 |
Correct |
513 ms |
37896 KB |
Output is correct |
30 |
Correct |
522 ms |
38732 KB |
Output is correct |
31 |
Correct |
516 ms |
38440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
14936 KB |
Output is correct |
2 |
Correct |
13 ms |
15448 KB |
Output is correct |
3 |
Correct |
13 ms |
15448 KB |
Output is correct |
4 |
Correct |
13 ms |
15448 KB |
Output is correct |
5 |
Correct |
631 ms |
36548 KB |
Output is correct |
6 |
Correct |
614 ms |
36344 KB |
Output is correct |
7 |
Correct |
816 ms |
35136 KB |
Output is correct |
8 |
Correct |
966 ms |
42948 KB |
Output is correct |
9 |
Correct |
1002 ms |
42936 KB |
Output is correct |
10 |
Correct |
984 ms |
43096 KB |
Output is correct |
11 |
Correct |
779 ms |
42948 KB |
Output is correct |
12 |
Correct |
848 ms |
42948 KB |
Output is correct |
13 |
Correct |
829 ms |
43200 KB |
Output is correct |
14 |
Correct |
548 ms |
42532 KB |
Output is correct |
15 |
Correct |
557 ms |
42280 KB |
Output is correct |
16 |
Correct |
619 ms |
42688 KB |
Output is correct |
17 |
Correct |
606 ms |
42436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
14936 KB |
Output is correct |
2 |
Correct |
3 ms |
14936 KB |
Output is correct |
3 |
Correct |
3 ms |
14936 KB |
Output is correct |
4 |
Correct |
3 ms |
14936 KB |
Output is correct |
5 |
Correct |
10 ms |
15200 KB |
Output is correct |
6 |
Correct |
12 ms |
15192 KB |
Output is correct |
7 |
Correct |
10 ms |
15192 KB |
Output is correct |
8 |
Correct |
12 ms |
15192 KB |
Output is correct |
9 |
Correct |
12 ms |
15192 KB |
Output is correct |
10 |
Correct |
12 ms |
15192 KB |
Output is correct |
11 |
Correct |
13 ms |
15192 KB |
Output is correct |
12 |
Correct |
12 ms |
15192 KB |
Output is correct |
13 |
Correct |
16 ms |
15448 KB |
Output is correct |
14 |
Correct |
13 ms |
15448 KB |
Output is correct |
15 |
Correct |
13 ms |
15452 KB |
Output is correct |
16 |
Correct |
13 ms |
15448 KB |
Output is correct |
17 |
Correct |
13 ms |
15448 KB |
Output is correct |
18 |
Correct |
13 ms |
15448 KB |
Output is correct |
19 |
Correct |
14 ms |
15440 KB |
Output is correct |
20 |
Correct |
11 ms |
15192 KB |
Output is correct |
21 |
Correct |
11 ms |
15196 KB |
Output is correct |
22 |
Correct |
12 ms |
15192 KB |
Output is correct |
23 |
Correct |
11 ms |
15192 KB |
Output is correct |
24 |
Correct |
11 ms |
15192 KB |
Output is correct |
25 |
Correct |
11 ms |
15396 KB |
Output is correct |
26 |
Correct |
10 ms |
15192 KB |
Output is correct |
27 |
Correct |
9 ms |
15236 KB |
Output is correct |
28 |
Correct |
10 ms |
15192 KB |
Output is correct |
29 |
Correct |
9 ms |
15236 KB |
Output is correct |
30 |
Correct |
12 ms |
15192 KB |
Output is correct |
31 |
Correct |
12 ms |
15192 KB |
Output is correct |
32 |
Correct |
14 ms |
15192 KB |
Output is correct |
33 |
Correct |
13 ms |
15448 KB |
Output is correct |
34 |
Correct |
13 ms |
15448 KB |
Output is correct |
35 |
Correct |
14 ms |
15448 KB |
Output is correct |
36 |
Correct |
3 ms |
14764 KB |
Output is correct |
37 |
Correct |
12 ms |
15192 KB |
Output is correct |
38 |
Correct |
15 ms |
15192 KB |
Output is correct |
39 |
Correct |
15 ms |
15192 KB |
Output is correct |
40 |
Correct |
576 ms |
33364 KB |
Output is correct |
41 |
Correct |
765 ms |
37340 KB |
Output is correct |
42 |
Correct |
703 ms |
36804 KB |
Output is correct |
43 |
Correct |
557 ms |
32704 KB |
Output is correct |
44 |
Correct |
534 ms |
32260 KB |
Output is correct |
45 |
Correct |
873 ms |
40304 KB |
Output is correct |
46 |
Correct |
854 ms |
40432 KB |
Output is correct |
47 |
Correct |
927 ms |
40128 KB |
Output is correct |
48 |
Correct |
907 ms |
40128 KB |
Output is correct |
49 |
Correct |
825 ms |
40320 KB |
Output is correct |
50 |
Correct |
956 ms |
48056 KB |
Output is correct |
51 |
Correct |
1008 ms |
48728 KB |
Output is correct |
52 |
Correct |
941 ms |
47812 KB |
Output is correct |
53 |
Correct |
883 ms |
40644 KB |
Output is correct |
54 |
Correct |
904 ms |
40828 KB |
Output is correct |
55 |
Correct |
946 ms |
40900 KB |
Output is correct |
56 |
Correct |
794 ms |
40596 KB |
Output is correct |
57 |
Correct |
789 ms |
40672 KB |
Output is correct |
58 |
Correct |
748 ms |
40456 KB |
Output is correct |
59 |
Correct |
748 ms |
40588 KB |
Output is correct |
60 |
Correct |
764 ms |
40100 KB |
Output is correct |
61 |
Correct |
695 ms |
40148 KB |
Output is correct |
62 |
Correct |
661 ms |
40436 KB |
Output is correct |
63 |
Correct |
478 ms |
38956 KB |
Output is correct |
64 |
Correct |
513 ms |
37896 KB |
Output is correct |
65 |
Correct |
522 ms |
38732 KB |
Output is correct |
66 |
Correct |
516 ms |
38440 KB |
Output is correct |
67 |
Correct |
2 ms |
14936 KB |
Output is correct |
68 |
Correct |
13 ms |
15448 KB |
Output is correct |
69 |
Correct |
13 ms |
15448 KB |
Output is correct |
70 |
Correct |
13 ms |
15448 KB |
Output is correct |
71 |
Correct |
631 ms |
36548 KB |
Output is correct |
72 |
Correct |
614 ms |
36344 KB |
Output is correct |
73 |
Correct |
816 ms |
35136 KB |
Output is correct |
74 |
Correct |
966 ms |
42948 KB |
Output is correct |
75 |
Correct |
1002 ms |
42936 KB |
Output is correct |
76 |
Correct |
984 ms |
43096 KB |
Output is correct |
77 |
Correct |
779 ms |
42948 KB |
Output is correct |
78 |
Correct |
848 ms |
42948 KB |
Output is correct |
79 |
Correct |
829 ms |
43200 KB |
Output is correct |
80 |
Correct |
548 ms |
42532 KB |
Output is correct |
81 |
Correct |
557 ms |
42280 KB |
Output is correct |
82 |
Correct |
619 ms |
42688 KB |
Output is correct |
83 |
Correct |
606 ms |
42436 KB |
Output is correct |
84 |
Correct |
661 ms |
33056 KB |
Output is correct |
85 |
Correct |
651 ms |
33128 KB |
Output is correct |
86 |
Correct |
623 ms |
32376 KB |
Output is correct |
87 |
Correct |
963 ms |
40284 KB |
Output is correct |
88 |
Correct |
926 ms |
40224 KB |
Output is correct |
89 |
Correct |
967 ms |
40300 KB |
Output is correct |
90 |
Correct |
964 ms |
40112 KB |
Output is correct |
91 |
Correct |
1119 ms |
40208 KB |
Output is correct |
92 |
Correct |
967 ms |
45696 KB |
Output is correct |
93 |
Correct |
950 ms |
47300 KB |
Output is correct |
94 |
Correct |
966 ms |
40728 KB |
Output is correct |
95 |
Correct |
896 ms |
40644 KB |
Output is correct |
96 |
Correct |
900 ms |
40744 KB |
Output is correct |
97 |
Correct |
961 ms |
40640 KB |
Output is correct |
98 |
Correct |
776 ms |
40656 KB |
Output is correct |
99 |
Correct |
772 ms |
40220 KB |
Output is correct |
100 |
Correct |
837 ms |
40372 KB |
Output is correct |
101 |
Correct |
763 ms |
40388 KB |
Output is correct |
102 |
Correct |
792 ms |
40728 KB |
Output is correct |
103 |
Correct |
731 ms |
40640 KB |
Output is correct |
104 |
Correct |
819 ms |
40808 KB |
Output is correct |
105 |
Correct |
548 ms |
38084 KB |
Output is correct |
106 |
Correct |
584 ms |
39156 KB |
Output is correct |
107 |
Correct |
653 ms |
38020 KB |
Output is correct |
108 |
Correct |
602 ms |
38500 KB |
Output is correct |