#include <bits/stdc++.h>
using namespace std;
#define int long long
const int NM = 1e5, LOG = 16;
struct checkpt{
int v, c;
};
struct query{
int id, s, t, lca, x, y, l, r, mid, res;
};
int N, M, Q, u[NM+5], v[NM+5], t = 0;
vector <int> adj[NM+5];
int parent[NM+5], h[NM+5], st[NM+5], en[NM+5];
int jump[NM+5][LOG+5];
checkpt a[NM+5];
query b[NM+5];
int bit[2*NM+5], bit2[2*NM+5];
int ans[NM+5];
void DFS(int u){
st[u] = ++t;
for (int i = 0; i < adj[u].size(); i++){
int v = adj[u][i];
if (h[v] != -1) continue;
parent[v] = u;
h[v] = h[u]+1;
DFS(v);
}
en[u] = ++t;
}
void build(){
for (int i = 1; i <= N; i++) jump[i][0] = parent[i];
for (int j = 1; j <= LOG; j++)
for (int i = 1; i <= N; i++)
if (jump[i][j-1] != -1) jump[i][j] = jump[jump[i][j-1]][j-1];
else jump[i][j] = -1;
}
int LCA(int u, int v){
if (h[u] < h[v]) swap(u, v);
for (int i = LOG; i >= 0; i--)
if (h[u]-(1<<i) >= h[v]) u = jump[u][i];
if (u == v) return u;
for (int i = LOG; i >= 0; i--)
if (jump[u][i] != -1 && jump[u][i] != jump[v][i]){
u = jump[u][i];
v = jump[v][i];
}
return parent[u];
}
bool cmp(checkpt a, checkpt b){
return a.c < b.c;
}
bool cmp2(query a, query b){
if (a.l > a.r) return 0;
if (b.l > b.r) return 1;
return a.mid < b.mid;
}
void update(int bit[NM+5], int p, int v){
while (p <= 2*N){
bit[p] += v;
p += p & (-p);
}
}
int get(int bit[NM+5], int p){
int res = 0;
while (p > 0){
res += bit[p];
p -= p & (-p);
}
return res;
}
int get_range(int bit[NM+5], int l, int r){
return get(bit, r)-get(bit, l-1);
}
int get_path(int bit[NM+5], int s, int t, int lca){
return get_range(bit, st[lca], st[s])+get_range(bit, st[lca], st[t])-2*get_range(bit, st[lca], st[lca]);
}
void pbs(){
sort(b+1, b+1+Q, cmp2);
memset(bit, 0, sizeof(bit));
memset(bit2, 0, sizeof(bit2));
for (int i = 1; i <= M; i++){
update(bit, st[a[i].v], 1);
update(bit, en[a[i].v], -1);
}
int j = 1;
for (int i = 1; i <= Q; i++){
if (b[i].l > b[i].r) break;
while (j <= b[i].mid){
update(bit, st[a[j].v], -1);
update(bit, en[a[j].v], 1);
update(bit2, st[a[j].v], a[j].c);
update(bit2, en[a[j].v], -a[j].c);
j++;
}
int tmp = get_path(bit2, b[i].s, b[i].t, b[i].lca);
if (tmp <= b[i].y){
b[i].res = get_path(bit, b[i].s, b[i].t, b[i].lca);
b[i].l = b[i].mid+1;
}
else b[i].r = b[i].mid-1;
b[i].mid = (b[i].l+b[i].r)/2;
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> Q;
for (int i = 1; i < N; i++){
cin >> u[i] >> v[i];
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
parent[1] = -1, h[1] = 0;
for (int i = 2; i <= N; i++) h[i] = -1;
DFS(1);
build();
for (int i = 1; i <= M; i++){
int p; cin >> p;
if (parent[v[p]] == u[p]) a[i].v = v[p]; else a[i].v = u[p];
cin >> a[i].c;
}
sort(a+1, a+1+M, cmp);
for (int i = 1; i <= Q; i++){
b[i].id = i;
cin >> b[i].s >> b[i].t >> b[i].x >> b[i].y;
if (st[b[i].s] > st[b[i].t]) swap(b[i].s, b[i].t);
b[i].lca = LCA(b[i].s, b[i].t);
b[i].l = 0, b[i].r = M, b[i].mid = M/2;
}
for (int i = 0; (1<<i) <= M+1; i++)
pbs();
for (int i = 1; i <= Q; i++){
if (b[i].res > b[i].x) ans[b[i].id] = -1;
else ans[b[i].id] = b[i].x-b[i].res;
}
for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
return 0;
}
Compilation message
currencies.cpp: In function 'void DFS(long long int)':
currencies.cpp:27:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (int i = 0; i < adj[u].size(); i++){
| ~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5760 KB |
Output is correct |
2 |
Correct |
3 ms |
5844 KB |
Output is correct |
3 |
Correct |
3 ms |
5844 KB |
Output is correct |
4 |
Correct |
3 ms |
5844 KB |
Output is correct |
5 |
Correct |
9 ms |
6628 KB |
Output is correct |
6 |
Correct |
10 ms |
6616 KB |
Output is correct |
7 |
Correct |
10 ms |
6428 KB |
Output is correct |
8 |
Correct |
13 ms |
6624 KB |
Output is correct |
9 |
Correct |
10 ms |
6664 KB |
Output is correct |
10 |
Correct |
10 ms |
6544 KB |
Output is correct |
11 |
Correct |
13 ms |
6640 KB |
Output is correct |
12 |
Correct |
11 ms |
6548 KB |
Output is correct |
13 |
Correct |
10 ms |
6668 KB |
Output is correct |
14 |
Correct |
11 ms |
6688 KB |
Output is correct |
15 |
Correct |
12 ms |
6688 KB |
Output is correct |
16 |
Correct |
12 ms |
6656 KB |
Output is correct |
17 |
Correct |
10 ms |
6612 KB |
Output is correct |
18 |
Correct |
12 ms |
6660 KB |
Output is correct |
19 |
Correct |
9 ms |
6612 KB |
Output is correct |
20 |
Correct |
11 ms |
6636 KB |
Output is correct |
21 |
Correct |
9 ms |
6640 KB |
Output is correct |
22 |
Correct |
9 ms |
6540 KB |
Output is correct |
23 |
Correct |
9 ms |
6612 KB |
Output is correct |
24 |
Correct |
9 ms |
6612 KB |
Output is correct |
25 |
Correct |
12 ms |
6644 KB |
Output is correct |
26 |
Correct |
12 ms |
6612 KB |
Output is correct |
27 |
Correct |
11 ms |
6540 KB |
Output is correct |
28 |
Correct |
9 ms |
6612 KB |
Output is correct |
29 |
Correct |
9 ms |
6540 KB |
Output is correct |
30 |
Correct |
10 ms |
6584 KB |
Output is correct |
31 |
Correct |
9 ms |
6644 KB |
Output is correct |
32 |
Correct |
9 ms |
6644 KB |
Output is correct |
33 |
Correct |
10 ms |
6740 KB |
Output is correct |
34 |
Correct |
10 ms |
6724 KB |
Output is correct |
35 |
Correct |
11 ms |
6672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5844 KB |
Output is correct |
2 |
Correct |
12 ms |
6532 KB |
Output is correct |
3 |
Correct |
9 ms |
6660 KB |
Output is correct |
4 |
Correct |
9 ms |
6620 KB |
Output is correct |
5 |
Correct |
516 ms |
37712 KB |
Output is correct |
6 |
Correct |
651 ms |
32596 KB |
Output is correct |
7 |
Correct |
621 ms |
35652 KB |
Output is correct |
8 |
Correct |
473 ms |
34436 KB |
Output is correct |
9 |
Correct |
473 ms |
33960 KB |
Output is correct |
10 |
Correct |
704 ms |
41224 KB |
Output is correct |
11 |
Correct |
719 ms |
41304 KB |
Output is correct |
12 |
Correct |
739 ms |
41228 KB |
Output is correct |
13 |
Correct |
717 ms |
41212 KB |
Output is correct |
14 |
Correct |
736 ms |
41208 KB |
Output is correct |
15 |
Correct |
786 ms |
45008 KB |
Output is correct |
16 |
Correct |
816 ms |
45312 KB |
Output is correct |
17 |
Correct |
785 ms |
44812 KB |
Output is correct |
18 |
Correct |
760 ms |
40848 KB |
Output is correct |
19 |
Correct |
781 ms |
40812 KB |
Output is correct |
20 |
Correct |
761 ms |
40836 KB |
Output is correct |
21 |
Correct |
614 ms |
41280 KB |
Output is correct |
22 |
Correct |
618 ms |
41272 KB |
Output is correct |
23 |
Correct |
624 ms |
41360 KB |
Output is correct |
24 |
Correct |
619 ms |
41280 KB |
Output is correct |
25 |
Correct |
627 ms |
41452 KB |
Output is correct |
26 |
Correct |
609 ms |
41344 KB |
Output is correct |
27 |
Correct |
619 ms |
41336 KB |
Output is correct |
28 |
Correct |
596 ms |
41208 KB |
Output is correct |
29 |
Correct |
574 ms |
41164 KB |
Output is correct |
30 |
Correct |
602 ms |
41212 KB |
Output is correct |
31 |
Correct |
607 ms |
41220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5844 KB |
Output is correct |
2 |
Correct |
10 ms |
6724 KB |
Output is correct |
3 |
Correct |
10 ms |
6664 KB |
Output is correct |
4 |
Correct |
10 ms |
6740 KB |
Output is correct |
5 |
Correct |
513 ms |
40552 KB |
Output is correct |
6 |
Correct |
492 ms |
39840 KB |
Output is correct |
7 |
Correct |
658 ms |
31256 KB |
Output is correct |
8 |
Correct |
831 ms |
45420 KB |
Output is correct |
9 |
Correct |
829 ms |
45544 KB |
Output is correct |
10 |
Correct |
805 ms |
45540 KB |
Output is correct |
11 |
Correct |
769 ms |
45548 KB |
Output is correct |
12 |
Correct |
694 ms |
45664 KB |
Output is correct |
13 |
Correct |
659 ms |
45676 KB |
Output is correct |
14 |
Correct |
612 ms |
45676 KB |
Output is correct |
15 |
Correct |
641 ms |
45488 KB |
Output is correct |
16 |
Correct |
656 ms |
45676 KB |
Output is correct |
17 |
Correct |
686 ms |
45544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5760 KB |
Output is correct |
2 |
Correct |
3 ms |
5844 KB |
Output is correct |
3 |
Correct |
3 ms |
5844 KB |
Output is correct |
4 |
Correct |
3 ms |
5844 KB |
Output is correct |
5 |
Correct |
9 ms |
6628 KB |
Output is correct |
6 |
Correct |
10 ms |
6616 KB |
Output is correct |
7 |
Correct |
10 ms |
6428 KB |
Output is correct |
8 |
Correct |
13 ms |
6624 KB |
Output is correct |
9 |
Correct |
10 ms |
6664 KB |
Output is correct |
10 |
Correct |
10 ms |
6544 KB |
Output is correct |
11 |
Correct |
13 ms |
6640 KB |
Output is correct |
12 |
Correct |
11 ms |
6548 KB |
Output is correct |
13 |
Correct |
10 ms |
6668 KB |
Output is correct |
14 |
Correct |
11 ms |
6688 KB |
Output is correct |
15 |
Correct |
12 ms |
6688 KB |
Output is correct |
16 |
Correct |
12 ms |
6656 KB |
Output is correct |
17 |
Correct |
10 ms |
6612 KB |
Output is correct |
18 |
Correct |
12 ms |
6660 KB |
Output is correct |
19 |
Correct |
9 ms |
6612 KB |
Output is correct |
20 |
Correct |
11 ms |
6636 KB |
Output is correct |
21 |
Correct |
9 ms |
6640 KB |
Output is correct |
22 |
Correct |
9 ms |
6540 KB |
Output is correct |
23 |
Correct |
9 ms |
6612 KB |
Output is correct |
24 |
Correct |
9 ms |
6612 KB |
Output is correct |
25 |
Correct |
12 ms |
6644 KB |
Output is correct |
26 |
Correct |
12 ms |
6612 KB |
Output is correct |
27 |
Correct |
11 ms |
6540 KB |
Output is correct |
28 |
Correct |
9 ms |
6612 KB |
Output is correct |
29 |
Correct |
9 ms |
6540 KB |
Output is correct |
30 |
Correct |
10 ms |
6584 KB |
Output is correct |
31 |
Correct |
9 ms |
6644 KB |
Output is correct |
32 |
Correct |
9 ms |
6644 KB |
Output is correct |
33 |
Correct |
10 ms |
6740 KB |
Output is correct |
34 |
Correct |
10 ms |
6724 KB |
Output is correct |
35 |
Correct |
11 ms |
6672 KB |
Output is correct |
36 |
Correct |
3 ms |
5844 KB |
Output is correct |
37 |
Correct |
12 ms |
6532 KB |
Output is correct |
38 |
Correct |
9 ms |
6660 KB |
Output is correct |
39 |
Correct |
9 ms |
6620 KB |
Output is correct |
40 |
Correct |
516 ms |
37712 KB |
Output is correct |
41 |
Correct |
651 ms |
32596 KB |
Output is correct |
42 |
Correct |
621 ms |
35652 KB |
Output is correct |
43 |
Correct |
473 ms |
34436 KB |
Output is correct |
44 |
Correct |
473 ms |
33960 KB |
Output is correct |
45 |
Correct |
704 ms |
41224 KB |
Output is correct |
46 |
Correct |
719 ms |
41304 KB |
Output is correct |
47 |
Correct |
739 ms |
41228 KB |
Output is correct |
48 |
Correct |
717 ms |
41212 KB |
Output is correct |
49 |
Correct |
736 ms |
41208 KB |
Output is correct |
50 |
Correct |
786 ms |
45008 KB |
Output is correct |
51 |
Correct |
816 ms |
45312 KB |
Output is correct |
52 |
Correct |
785 ms |
44812 KB |
Output is correct |
53 |
Correct |
760 ms |
40848 KB |
Output is correct |
54 |
Correct |
781 ms |
40812 KB |
Output is correct |
55 |
Correct |
761 ms |
40836 KB |
Output is correct |
56 |
Correct |
614 ms |
41280 KB |
Output is correct |
57 |
Correct |
618 ms |
41272 KB |
Output is correct |
58 |
Correct |
624 ms |
41360 KB |
Output is correct |
59 |
Correct |
619 ms |
41280 KB |
Output is correct |
60 |
Correct |
627 ms |
41452 KB |
Output is correct |
61 |
Correct |
609 ms |
41344 KB |
Output is correct |
62 |
Correct |
619 ms |
41336 KB |
Output is correct |
63 |
Correct |
596 ms |
41208 KB |
Output is correct |
64 |
Correct |
574 ms |
41164 KB |
Output is correct |
65 |
Correct |
602 ms |
41212 KB |
Output is correct |
66 |
Correct |
607 ms |
41220 KB |
Output is correct |
67 |
Correct |
3 ms |
5844 KB |
Output is correct |
68 |
Correct |
10 ms |
6724 KB |
Output is correct |
69 |
Correct |
10 ms |
6664 KB |
Output is correct |
70 |
Correct |
10 ms |
6740 KB |
Output is correct |
71 |
Correct |
513 ms |
40552 KB |
Output is correct |
72 |
Correct |
492 ms |
39840 KB |
Output is correct |
73 |
Correct |
658 ms |
31256 KB |
Output is correct |
74 |
Correct |
831 ms |
45420 KB |
Output is correct |
75 |
Correct |
829 ms |
45544 KB |
Output is correct |
76 |
Correct |
805 ms |
45540 KB |
Output is correct |
77 |
Correct |
769 ms |
45548 KB |
Output is correct |
78 |
Correct |
694 ms |
45664 KB |
Output is correct |
79 |
Correct |
659 ms |
45676 KB |
Output is correct |
80 |
Correct |
612 ms |
45676 KB |
Output is correct |
81 |
Correct |
641 ms |
45488 KB |
Output is correct |
82 |
Correct |
656 ms |
45676 KB |
Output is correct |
83 |
Correct |
686 ms |
45544 KB |
Output is correct |
84 |
Correct |
540 ms |
33992 KB |
Output is correct |
85 |
Correct |
563 ms |
27616 KB |
Output is correct |
86 |
Correct |
494 ms |
27284 KB |
Output is correct |
87 |
Correct |
738 ms |
41340 KB |
Output is correct |
88 |
Correct |
756 ms |
41360 KB |
Output is correct |
89 |
Correct |
756 ms |
41340 KB |
Output is correct |
90 |
Correct |
798 ms |
41340 KB |
Output is correct |
91 |
Correct |
784 ms |
41344 KB |
Output is correct |
92 |
Correct |
851 ms |
43768 KB |
Output is correct |
93 |
Correct |
849 ms |
44908 KB |
Output is correct |
94 |
Correct |
945 ms |
41096 KB |
Output is correct |
95 |
Correct |
876 ms |
41108 KB |
Output is correct |
96 |
Correct |
929 ms |
41096 KB |
Output is correct |
97 |
Correct |
854 ms |
41088 KB |
Output is correct |
98 |
Correct |
716 ms |
41532 KB |
Output is correct |
99 |
Correct |
703 ms |
41620 KB |
Output is correct |
100 |
Correct |
664 ms |
41604 KB |
Output is correct |
101 |
Correct |
651 ms |
41516 KB |
Output is correct |
102 |
Correct |
674 ms |
41604 KB |
Output is correct |
103 |
Correct |
697 ms |
41592 KB |
Output is correct |
104 |
Correct |
691 ms |
41596 KB |
Output is correct |
105 |
Correct |
701 ms |
41492 KB |
Output is correct |
106 |
Correct |
694 ms |
41468 KB |
Output is correct |
107 |
Correct |
700 ms |
41396 KB |
Output is correct |
108 |
Correct |
642 ms |
41364 KB |
Output is correct |