#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
const int MAXN = 1e5 + 7;
const int INF = 1e18 + 7;
const int MOD = 1e9 + 7;
const int base = 1<<18;
const int LOG = 18;
const int A = 26;
const int PROD = 2 * MAXN;
const int MAX = 2e3 + 7;
const int SQ = 220;
struct interval {
int lo, hi, mid;
};
vector<pair<int, int>> G[MAXN];
vector<int> mids[MAXN];
pair<int, int> checkpoints[MAXN];
tuple<int, int, int, int> que[MAXN];
pii tree[2 * base];
int queriesLCA[MAXN];
int pre[MAXN], post[MAXN];
int jmp[MAXN][LOG];
int edges[MAXN];
int depth[MAXN];
int ans[MAXN];
interval bin[MAXN];
int c = 0;
int n, m, q;
void update(int v, pair<int, int> val){
v += base;
tree[v].fi += val.fi;
tree[v].se += val.se;
v /= 2;
while(v > 0){
tree[v].fi = tree[2 * v].fi + tree[2 * v + 1].fi;
tree[v].se = tree[2 * v].se + tree[2 * v + 1].se;
v /= 2;
}
}
pair<int, int> query(int a, int b){
a += base - 1;
b += base + 1;
pair<int, int> res = {0, 0};
while(a/2 != b/2){
if(a%2 == 0){
res.fi += tree[a + 1].fi;
res.se += tree[a + 1].se;
}
if(b%2 == 1){
res.fi += tree[b - 1].fi;
res.se += tree[b - 1].se;
}
a /= 2; b /= 2;
}
return res;
}
void DFS(int v, int p){
depth[v] = depth[p] + 1;
pre[v] = ++c;
jmp[v][0] = p;
for(int j = 1; j < LOG; j++){
jmp[v][j] = jmp[jmp[v][j - 1]][j - 1];
}
for(auto [u, id] : G[v]){
if(u == p) continue;
edges[id] = u;
DFS(u, v);
}
post[v] = ++c;
}
int lca(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for(int i = 0; i < LOG; i++){
if((1<<i) & diff){
u = jmp[u][i];
}
}
if(u == v) return u;
for(int i = LOG - 1; i >= 0; i--){
if(jmp[u][i] != jmp[v][i]){
u = jmp[u][i];
v = jmp[v][i];
}
}
return jmp[v][0];
}
void treeclear(){
for(int i = 0; i < 2 * base; i++){
tree[i] = {0, 0};
}
}
bool check(tuple<int, int, int, int> a, int v){
auto [s, t, x, y] = a;
if(depth[t] < depth[s]) swap(s, t);
pair<int, int> res = query(pre[queriesLCA[v]], pre[t]);
res.fi -= tree[pre[queriesLCA[v]] + base].fi;
res.se -= tree[pre[queriesLCA[v]] + base].se;
if(queriesLCA[v] != s){
pair<int, int> x = query(pre[queriesLCA[v]], pre[s]);
x.fi -= tree[pre[queriesLCA[v]] + base].fi;
x.se -= tree[pre[queriesLCA[v]] + base].se;
res.fi += x.fi;
res.se += x.se;
}
return res.fi <= y;
}
void parallel_binsearch(){
int left = q;
while(left){
for(int i = 0; i <= m; i++){
update(pre[edges[checkpoints[i].se]], {checkpoints[i].fi, 1});
update(post[edges[checkpoints[i].se]], {-checkpoints[i].fi, -1});
for(auto cand : mids[i]){
if(check(que[cand], cand)) bin[cand].lo = i + 1;
else bin[cand].hi = i;
bin[cand].mid = (bin[cand].lo + bin[cand].hi)/2;
if(bin[cand].lo == bin[cand].hi) left--;
else mids[bin[cand].mid].push_back(cand);
}
mids[i].clear();
}
treeclear();
}
}
void save_res(int v, bool save){
auto [s, t, x, y] = que[v];
if(depth[t] < depth[s]) swap(s, t);
pair<int, int> res = query(pre[queriesLCA[v]], pre[t]);
res.fi -= tree[pre[queriesLCA[v]] + base].fi;
res.se -= tree[pre[queriesLCA[v]] + base].se;
if(queriesLCA[v] != s){
pair<int, int> x = query(pre[queriesLCA[v]], pre[s]);
x.fi -= tree[pre[queriesLCA[v]] + base].fi;
x.se -= tree[pre[queriesLCA[v]] + base].se;
res.fi += x.fi;
res.se += x.se;
}
if(save){
ans[v] = res.se;
if(res.fi > y) ans[v] = max(ans[v] - 1, 0LL);
}
else ans[v] = x - max(0LL, res.se - ans[v]);
}
void rozw(){
for(int i = 1; i <= q; i++){
mids[bin[i].lo].push_back(i);
}
for(int i = 0; i <= m; i++){
update(pre[edges[checkpoints[i].se]], {checkpoints[i].fi, 1});
update(post[edges[checkpoints[i].se]], {-checkpoints[i].fi, -1});
for(auto cand : mids[i]){
save_res(cand, 1);
}
mids[i].clear();
}
for(int i = 1; i <= q; i++){
save_res(i, 0);
}
}
void solve(){
cin >> n >> m >> q;
for(int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
G[a].push_back({b, i});
G[b].push_back({a, i});
}
for(int i = 1; i <= m; i++){
int p, c;
cin >> p >> c;
checkpoints[i] = {c, p};
}
DFS(1, 1);
for(int i = 1; i <= q; i++){
int s, t, x, y;
cin >> s >> t >> x >> y;
que[i] = {s, t, x, y};
queriesLCA[i] = lca(s, t);
bin[i].lo = 0;
bin[i].hi = m;
bin[i].mid = m/2;
mids[bin[i].mid].push_back(i);
}
sort(checkpoints + 1, checkpoints + m + 1);
parallel_binsearch();
rozw();
for(int i = 1; i <= q; i++){
cout << max(ans[i], -1LL) << '\n';
}
}
bool multi = 0;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
if(multi) cin >> t;
while(t--) solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
22616 KB |
Output is correct |
2 |
Correct |
5 ms |
22620 KB |
Output is correct |
3 |
Correct |
4 ms |
22620 KB |
Output is correct |
4 |
Correct |
5 ms |
22620 KB |
Output is correct |
5 |
Correct |
13 ms |
22908 KB |
Output is correct |
6 |
Correct |
15 ms |
23120 KB |
Output is correct |
7 |
Correct |
14 ms |
22876 KB |
Output is correct |
8 |
Correct |
21 ms |
23128 KB |
Output is correct |
9 |
Correct |
18 ms |
22992 KB |
Output is correct |
10 |
Correct |
17 ms |
23384 KB |
Output is correct |
11 |
Correct |
18 ms |
23132 KB |
Output is correct |
12 |
Correct |
16 ms |
23132 KB |
Output is correct |
13 |
Correct |
15 ms |
23132 KB |
Output is correct |
14 |
Correct |
16 ms |
23172 KB |
Output is correct |
15 |
Correct |
16 ms |
23132 KB |
Output is correct |
16 |
Correct |
15 ms |
23132 KB |
Output is correct |
17 |
Correct |
16 ms |
23132 KB |
Output is correct |
18 |
Correct |
15 ms |
23132 KB |
Output is correct |
19 |
Correct |
15 ms |
23132 KB |
Output is correct |
20 |
Correct |
15 ms |
23128 KB |
Output is correct |
21 |
Correct |
15 ms |
23380 KB |
Output is correct |
22 |
Correct |
15 ms |
23132 KB |
Output is correct |
23 |
Correct |
14 ms |
23132 KB |
Output is correct |
24 |
Correct |
14 ms |
23108 KB |
Output is correct |
25 |
Correct |
15 ms |
23132 KB |
Output is correct |
26 |
Correct |
12 ms |
23132 KB |
Output is correct |
27 |
Correct |
11 ms |
23132 KB |
Output is correct |
28 |
Correct |
18 ms |
23356 KB |
Output is correct |
29 |
Correct |
12 ms |
22876 KB |
Output is correct |
30 |
Correct |
16 ms |
23132 KB |
Output is correct |
31 |
Correct |
17 ms |
23148 KB |
Output is correct |
32 |
Correct |
17 ms |
23128 KB |
Output is correct |
33 |
Correct |
14 ms |
23132 KB |
Output is correct |
34 |
Correct |
15 ms |
23132 KB |
Output is correct |
35 |
Correct |
14 ms |
23132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
22616 KB |
Output is correct |
2 |
Correct |
15 ms |
23132 KB |
Output is correct |
3 |
Correct |
15 ms |
23132 KB |
Output is correct |
4 |
Correct |
16 ms |
23128 KB |
Output is correct |
5 |
Correct |
649 ms |
59048 KB |
Output is correct |
6 |
Correct |
788 ms |
60232 KB |
Output is correct |
7 |
Correct |
810 ms |
61084 KB |
Output is correct |
8 |
Correct |
613 ms |
58196 KB |
Output is correct |
9 |
Correct |
646 ms |
57432 KB |
Output is correct |
10 |
Correct |
1045 ms |
67468 KB |
Output is correct |
11 |
Correct |
1061 ms |
67856 KB |
Output is correct |
12 |
Correct |
1052 ms |
67388 KB |
Output is correct |
13 |
Correct |
1115 ms |
67936 KB |
Output is correct |
14 |
Correct |
993 ms |
67508 KB |
Output is correct |
15 |
Correct |
1012 ms |
72300 KB |
Output is correct |
16 |
Correct |
958 ms |
72664 KB |
Output is correct |
17 |
Correct |
938 ms |
72004 KB |
Output is correct |
18 |
Correct |
1195 ms |
68008 KB |
Output is correct |
19 |
Correct |
1130 ms |
68300 KB |
Output is correct |
20 |
Correct |
1196 ms |
68068 KB |
Output is correct |
21 |
Correct |
846 ms |
67644 KB |
Output is correct |
22 |
Correct |
807 ms |
67544 KB |
Output is correct |
23 |
Correct |
830 ms |
67460 KB |
Output is correct |
24 |
Correct |
796 ms |
67548 KB |
Output is correct |
25 |
Correct |
825 ms |
67276 KB |
Output is correct |
26 |
Correct |
781 ms |
67096 KB |
Output is correct |
27 |
Correct |
797 ms |
67520 KB |
Output is correct |
28 |
Correct |
482 ms |
65364 KB |
Output is correct |
29 |
Correct |
470 ms |
64212 KB |
Output is correct |
30 |
Correct |
604 ms |
64840 KB |
Output is correct |
31 |
Correct |
740 ms |
64812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
22620 KB |
Output is correct |
2 |
Correct |
14 ms |
23220 KB |
Output is correct |
3 |
Correct |
15 ms |
23132 KB |
Output is correct |
4 |
Correct |
14 ms |
23132 KB |
Output is correct |
5 |
Correct |
576 ms |
63392 KB |
Output is correct |
6 |
Correct |
586 ms |
63364 KB |
Output is correct |
7 |
Correct |
686 ms |
57760 KB |
Output is correct |
8 |
Correct |
1087 ms |
72364 KB |
Output is correct |
9 |
Correct |
1192 ms |
72316 KB |
Output is correct |
10 |
Correct |
1112 ms |
72688 KB |
Output is correct |
11 |
Correct |
850 ms |
72852 KB |
Output is correct |
12 |
Correct |
869 ms |
72740 KB |
Output is correct |
13 |
Correct |
828 ms |
72392 KB |
Output is correct |
14 |
Correct |
803 ms |
71992 KB |
Output is correct |
15 |
Correct |
686 ms |
72132 KB |
Output is correct |
16 |
Correct |
933 ms |
72388 KB |
Output is correct |
17 |
Correct |
761 ms |
72680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
22616 KB |
Output is correct |
2 |
Correct |
5 ms |
22620 KB |
Output is correct |
3 |
Correct |
4 ms |
22620 KB |
Output is correct |
4 |
Correct |
5 ms |
22620 KB |
Output is correct |
5 |
Correct |
13 ms |
22908 KB |
Output is correct |
6 |
Correct |
15 ms |
23120 KB |
Output is correct |
7 |
Correct |
14 ms |
22876 KB |
Output is correct |
8 |
Correct |
21 ms |
23128 KB |
Output is correct |
9 |
Correct |
18 ms |
22992 KB |
Output is correct |
10 |
Correct |
17 ms |
23384 KB |
Output is correct |
11 |
Correct |
18 ms |
23132 KB |
Output is correct |
12 |
Correct |
16 ms |
23132 KB |
Output is correct |
13 |
Correct |
15 ms |
23132 KB |
Output is correct |
14 |
Correct |
16 ms |
23172 KB |
Output is correct |
15 |
Correct |
16 ms |
23132 KB |
Output is correct |
16 |
Correct |
15 ms |
23132 KB |
Output is correct |
17 |
Correct |
16 ms |
23132 KB |
Output is correct |
18 |
Correct |
15 ms |
23132 KB |
Output is correct |
19 |
Correct |
15 ms |
23132 KB |
Output is correct |
20 |
Correct |
15 ms |
23128 KB |
Output is correct |
21 |
Correct |
15 ms |
23380 KB |
Output is correct |
22 |
Correct |
15 ms |
23132 KB |
Output is correct |
23 |
Correct |
14 ms |
23132 KB |
Output is correct |
24 |
Correct |
14 ms |
23108 KB |
Output is correct |
25 |
Correct |
15 ms |
23132 KB |
Output is correct |
26 |
Correct |
12 ms |
23132 KB |
Output is correct |
27 |
Correct |
11 ms |
23132 KB |
Output is correct |
28 |
Correct |
18 ms |
23356 KB |
Output is correct |
29 |
Correct |
12 ms |
22876 KB |
Output is correct |
30 |
Correct |
16 ms |
23132 KB |
Output is correct |
31 |
Correct |
17 ms |
23148 KB |
Output is correct |
32 |
Correct |
17 ms |
23128 KB |
Output is correct |
33 |
Correct |
14 ms |
23132 KB |
Output is correct |
34 |
Correct |
15 ms |
23132 KB |
Output is correct |
35 |
Correct |
14 ms |
23132 KB |
Output is correct |
36 |
Correct |
6 ms |
22616 KB |
Output is correct |
37 |
Correct |
15 ms |
23132 KB |
Output is correct |
38 |
Correct |
15 ms |
23132 KB |
Output is correct |
39 |
Correct |
16 ms |
23128 KB |
Output is correct |
40 |
Correct |
649 ms |
59048 KB |
Output is correct |
41 |
Correct |
788 ms |
60232 KB |
Output is correct |
42 |
Correct |
810 ms |
61084 KB |
Output is correct |
43 |
Correct |
613 ms |
58196 KB |
Output is correct |
44 |
Correct |
646 ms |
57432 KB |
Output is correct |
45 |
Correct |
1045 ms |
67468 KB |
Output is correct |
46 |
Correct |
1061 ms |
67856 KB |
Output is correct |
47 |
Correct |
1052 ms |
67388 KB |
Output is correct |
48 |
Correct |
1115 ms |
67936 KB |
Output is correct |
49 |
Correct |
993 ms |
67508 KB |
Output is correct |
50 |
Correct |
1012 ms |
72300 KB |
Output is correct |
51 |
Correct |
958 ms |
72664 KB |
Output is correct |
52 |
Correct |
938 ms |
72004 KB |
Output is correct |
53 |
Correct |
1195 ms |
68008 KB |
Output is correct |
54 |
Correct |
1130 ms |
68300 KB |
Output is correct |
55 |
Correct |
1196 ms |
68068 KB |
Output is correct |
56 |
Correct |
846 ms |
67644 KB |
Output is correct |
57 |
Correct |
807 ms |
67544 KB |
Output is correct |
58 |
Correct |
830 ms |
67460 KB |
Output is correct |
59 |
Correct |
796 ms |
67548 KB |
Output is correct |
60 |
Correct |
825 ms |
67276 KB |
Output is correct |
61 |
Correct |
781 ms |
67096 KB |
Output is correct |
62 |
Correct |
797 ms |
67520 KB |
Output is correct |
63 |
Correct |
482 ms |
65364 KB |
Output is correct |
64 |
Correct |
470 ms |
64212 KB |
Output is correct |
65 |
Correct |
604 ms |
64840 KB |
Output is correct |
66 |
Correct |
740 ms |
64812 KB |
Output is correct |
67 |
Correct |
4 ms |
22620 KB |
Output is correct |
68 |
Correct |
14 ms |
23220 KB |
Output is correct |
69 |
Correct |
15 ms |
23132 KB |
Output is correct |
70 |
Correct |
14 ms |
23132 KB |
Output is correct |
71 |
Correct |
576 ms |
63392 KB |
Output is correct |
72 |
Correct |
586 ms |
63364 KB |
Output is correct |
73 |
Correct |
686 ms |
57760 KB |
Output is correct |
74 |
Correct |
1087 ms |
72364 KB |
Output is correct |
75 |
Correct |
1192 ms |
72316 KB |
Output is correct |
76 |
Correct |
1112 ms |
72688 KB |
Output is correct |
77 |
Correct |
850 ms |
72852 KB |
Output is correct |
78 |
Correct |
869 ms |
72740 KB |
Output is correct |
79 |
Correct |
828 ms |
72392 KB |
Output is correct |
80 |
Correct |
803 ms |
71992 KB |
Output is correct |
81 |
Correct |
686 ms |
72132 KB |
Output is correct |
82 |
Correct |
933 ms |
72388 KB |
Output is correct |
83 |
Correct |
761 ms |
72680 KB |
Output is correct |
84 |
Correct |
662 ms |
56508 KB |
Output is correct |
85 |
Correct |
680 ms |
52696 KB |
Output is correct |
86 |
Correct |
625 ms |
51928 KB |
Output is correct |
87 |
Correct |
1212 ms |
67428 KB |
Output is correct |
88 |
Correct |
1121 ms |
67788 KB |
Output is correct |
89 |
Correct |
1318 ms |
67260 KB |
Output is correct |
90 |
Correct |
1164 ms |
67752 KB |
Output is correct |
91 |
Correct |
1226 ms |
67736 KB |
Output is correct |
92 |
Correct |
1204 ms |
71032 KB |
Output is correct |
93 |
Correct |
1134 ms |
71804 KB |
Output is correct |
94 |
Correct |
1265 ms |
67972 KB |
Output is correct |
95 |
Correct |
1310 ms |
68020 KB |
Output is correct |
96 |
Correct |
1255 ms |
68020 KB |
Output is correct |
97 |
Correct |
1327 ms |
67824 KB |
Output is correct |
98 |
Correct |
1083 ms |
67324 KB |
Output is correct |
99 |
Correct |
1012 ms |
66832 KB |
Output is correct |
100 |
Correct |
1132 ms |
67168 KB |
Output is correct |
101 |
Correct |
1090 ms |
67460 KB |
Output is correct |
102 |
Correct |
918 ms |
67912 KB |
Output is correct |
103 |
Correct |
931 ms |
68360 KB |
Output is correct |
104 |
Correct |
975 ms |
68156 KB |
Output is correct |
105 |
Correct |
569 ms |
64712 KB |
Output is correct |
106 |
Correct |
543 ms |
64928 KB |
Output is correct |
107 |
Correct |
709 ms |
64224 KB |
Output is correct |
108 |
Correct |
713 ms |
64204 KB |
Output is correct |