#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)
struct FenwickTree{
int n; vector<int> t;
void init(int _n){
n=_n;
t.assign(n+1, 0);
}
void update(int pos, int val){
for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
}
void update(int l, int r, int val){
update(l, val);
update(r+1, -val);
}
int get(int pos){
int ans=0;
for (int i=pos; i; i-=i&(-i)) ans+=t[i];
return ans;
}
} bit, bit2;
struct nigga{
int s, t, x, y;
nigga(int a=0, int b=0, int c=0, int d=0): s(a), t(b), x(c), y(d){};
};
const int N=1e5+1, LG=17;
int n, m, q, tdfs, tin[N], tout[N], up[N][LG], dep[N], l[N], r[N], ans[N];
vector<int> g[N], vv[N];
nigga a[N];
void dfs(int u){
tin[u]=++tdfs;
dep[u]=dep[up[u][0]]+1;
for (int v:g[u]) if (v!=up[u][0]){
up[v][0]=u;
for (int k=1; k<LG; ++k) up[v][k]=up[up[v][k-1]][k-1];
dfs(v);
}
tout[u]=tdfs;
}
int lca(int u, int v){
if (dep[u]!=dep[v]){
if (dep[u]<dep[v]) swap(u, v);
int d=dep[u]-dep[v];
for (int k=0; k<LG; ++k) if (d>>k&1) u=up[u][k];
}
if (u==v) return u;
for (int k=LG-1; k>=0; --k) if (up[u][k]!=up[v][k]) u=up[u][k], v=up[v][k];
return up[u][0];
}
void solve(int tc){
// cout << "Case #" << tc << ": ";
cin >> n >> m >> q;
vector<pair<int, int>> edges;
for (int i=1; i<n; ++i){
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
edges.emplace_back(x, y);
}
dfs(1);
vector<pair<int, int>> pts{{0, 0}};
bit2.init(n);
for (int i=1; i<=m; ++i){
int p, c; cin >> p >> c; --p;
int x=edges[p].first, y=edges[p].second;
if (tin[x]>tin[y]) swap(x, y);
pts.emplace_back(c, y);
bit2.update(tin[y], tout[y], 1);
}
sort(all(pts));
for (int i=1; i<=q; ++i){
cin >> a[i].s >> a[i].t >> a[i].x >> a[i].y;
l[i]=0, r[i]=sz(pts)-1;
}
for (int rep=0; rep<LG; ++rep){
for (int i=1; i<=q; ++i) if (l[i]<=r[i]) vv[(l[i]+r[i])>>1].push_back(i);
bit.init(n);
for (int i=0; i<sz(pts); ++i){
if (i) bit.update(tin[pts[i].second], tout[pts[i].second], pts[i].first);
for (int j:vv[i]){
int u=a[j].s, v=a[j].t, w=lca(u, v);
int sum_silver=bit.get(tin[u])+bit.get(tin[v])-(bit.get(tin[w])<<1);
if (sum_silver<=a[j].y) l[j]=i+1;
else r[j]=i-1;
}
vv[i].clear();
}
}
for (int i=1; i<=q; ++i) vv[r[i]].push_back(i);
bit.init(n);
for (int i=0; i<sz(pts); ++i){
if (i) bit.update(tin[pts[i].second], tout[pts[i].second], 1);
for (int j:vv[i]){
int u=a[j].s, v=a[j].t, w=lca(u, v);
int cnt_silver=bit.get(tin[u])+bit.get(tin[v])-(bit.get(tin[w])<<1);
int cnt_pts=bit2.get(tin[u])+bit2.get(tin[v])-(bit2.get(tin[w])<<1);
int cnt_gold=cnt_pts-cnt_silver;
ans[j]=a[j].x-min(cnt_gold, a[j].x+1);
}
vv[i].clear();
}
for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int ntests=1;
// cin >> ntests;
for (int i=1; i<=ntests; ++i) solve(i);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8148 KB |
Output is correct |
2 |
Correct |
4 ms |
8148 KB |
Output is correct |
3 |
Correct |
4 ms |
8148 KB |
Output is correct |
4 |
Correct |
3 ms |
8148 KB |
Output is correct |
5 |
Correct |
9 ms |
8808 KB |
Output is correct |
6 |
Correct |
9 ms |
9044 KB |
Output is correct |
7 |
Correct |
8 ms |
8800 KB |
Output is correct |
8 |
Correct |
10 ms |
9044 KB |
Output is correct |
9 |
Correct |
10 ms |
9044 KB |
Output is correct |
10 |
Correct |
11 ms |
9044 KB |
Output is correct |
11 |
Correct |
10 ms |
9032 KB |
Output is correct |
12 |
Correct |
12 ms |
9092 KB |
Output is correct |
13 |
Correct |
9 ms |
9172 KB |
Output is correct |
14 |
Correct |
10 ms |
9116 KB |
Output is correct |
15 |
Correct |
12 ms |
9188 KB |
Output is correct |
16 |
Correct |
10 ms |
9044 KB |
Output is correct |
17 |
Correct |
10 ms |
9044 KB |
Output is correct |
18 |
Correct |
10 ms |
9084 KB |
Output is correct |
19 |
Correct |
9 ms |
9068 KB |
Output is correct |
20 |
Correct |
9 ms |
9044 KB |
Output is correct |
21 |
Correct |
12 ms |
9044 KB |
Output is correct |
22 |
Correct |
9 ms |
9044 KB |
Output is correct |
23 |
Correct |
9 ms |
9044 KB |
Output is correct |
24 |
Correct |
9 ms |
9076 KB |
Output is correct |
25 |
Correct |
9 ms |
9084 KB |
Output is correct |
26 |
Correct |
8 ms |
9016 KB |
Output is correct |
27 |
Correct |
8 ms |
9044 KB |
Output is correct |
28 |
Correct |
8 ms |
9064 KB |
Output is correct |
29 |
Correct |
9 ms |
8936 KB |
Output is correct |
30 |
Correct |
10 ms |
9076 KB |
Output is correct |
31 |
Correct |
9 ms |
9044 KB |
Output is correct |
32 |
Correct |
10 ms |
9004 KB |
Output is correct |
33 |
Correct |
9 ms |
9124 KB |
Output is correct |
34 |
Correct |
10 ms |
9060 KB |
Output is correct |
35 |
Correct |
11 ms |
9044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8148 KB |
Output is correct |
2 |
Correct |
9 ms |
9008 KB |
Output is correct |
3 |
Correct |
10 ms |
9068 KB |
Output is correct |
4 |
Correct |
9 ms |
9044 KB |
Output is correct |
5 |
Correct |
565 ms |
48784 KB |
Output is correct |
6 |
Correct |
650 ms |
48564 KB |
Output is correct |
7 |
Correct |
734 ms |
49928 KB |
Output is correct |
8 |
Correct |
664 ms |
45416 KB |
Output is correct |
9 |
Correct |
649 ms |
44748 KB |
Output is correct |
10 |
Correct |
1132 ms |
57828 KB |
Output is correct |
11 |
Correct |
1062 ms |
57588 KB |
Output is correct |
12 |
Correct |
1122 ms |
57548 KB |
Output is correct |
13 |
Correct |
1072 ms |
57820 KB |
Output is correct |
14 |
Correct |
1016 ms |
57700 KB |
Output is correct |
15 |
Correct |
1610 ms |
62264 KB |
Output is correct |
16 |
Correct |
1425 ms |
62692 KB |
Output is correct |
17 |
Correct |
1583 ms |
61964 KB |
Output is correct |
18 |
Correct |
1443 ms |
57656 KB |
Output is correct |
19 |
Correct |
1606 ms |
58012 KB |
Output is correct |
20 |
Correct |
1438 ms |
58008 KB |
Output is correct |
21 |
Correct |
707 ms |
58144 KB |
Output is correct |
22 |
Correct |
700 ms |
58160 KB |
Output is correct |
23 |
Correct |
712 ms |
58348 KB |
Output is correct |
24 |
Correct |
691 ms |
58172 KB |
Output is correct |
25 |
Correct |
743 ms |
57368 KB |
Output is correct |
26 |
Correct |
726 ms |
57172 KB |
Output is correct |
27 |
Correct |
764 ms |
57664 KB |
Output is correct |
28 |
Correct |
349 ms |
56908 KB |
Output is correct |
29 |
Correct |
330 ms |
55292 KB |
Output is correct |
30 |
Correct |
414 ms |
55884 KB |
Output is correct |
31 |
Correct |
419 ms |
55220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8160 KB |
Output is correct |
2 |
Correct |
8 ms |
9172 KB |
Output is correct |
3 |
Correct |
9 ms |
9044 KB |
Output is correct |
4 |
Correct |
9 ms |
9064 KB |
Output is correct |
5 |
Correct |
683 ms |
51772 KB |
Output is correct |
6 |
Correct |
664 ms |
51004 KB |
Output is correct |
7 |
Correct |
589 ms |
46200 KB |
Output is correct |
8 |
Correct |
1161 ms |
62696 KB |
Output is correct |
9 |
Correct |
1112 ms |
62832 KB |
Output is correct |
10 |
Correct |
1158 ms |
62748 KB |
Output is correct |
11 |
Correct |
677 ms |
62664 KB |
Output is correct |
12 |
Correct |
636 ms |
62696 KB |
Output is correct |
13 |
Correct |
665 ms |
62616 KB |
Output is correct |
14 |
Correct |
268 ms |
62476 KB |
Output is correct |
15 |
Correct |
255 ms |
62384 KB |
Output is correct |
16 |
Correct |
438 ms |
62768 KB |
Output is correct |
17 |
Correct |
432 ms |
62620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8148 KB |
Output is correct |
2 |
Correct |
4 ms |
8148 KB |
Output is correct |
3 |
Correct |
4 ms |
8148 KB |
Output is correct |
4 |
Correct |
3 ms |
8148 KB |
Output is correct |
5 |
Correct |
9 ms |
8808 KB |
Output is correct |
6 |
Correct |
9 ms |
9044 KB |
Output is correct |
7 |
Correct |
8 ms |
8800 KB |
Output is correct |
8 |
Correct |
10 ms |
9044 KB |
Output is correct |
9 |
Correct |
10 ms |
9044 KB |
Output is correct |
10 |
Correct |
11 ms |
9044 KB |
Output is correct |
11 |
Correct |
10 ms |
9032 KB |
Output is correct |
12 |
Correct |
12 ms |
9092 KB |
Output is correct |
13 |
Correct |
9 ms |
9172 KB |
Output is correct |
14 |
Correct |
10 ms |
9116 KB |
Output is correct |
15 |
Correct |
12 ms |
9188 KB |
Output is correct |
16 |
Correct |
10 ms |
9044 KB |
Output is correct |
17 |
Correct |
10 ms |
9044 KB |
Output is correct |
18 |
Correct |
10 ms |
9084 KB |
Output is correct |
19 |
Correct |
9 ms |
9068 KB |
Output is correct |
20 |
Correct |
9 ms |
9044 KB |
Output is correct |
21 |
Correct |
12 ms |
9044 KB |
Output is correct |
22 |
Correct |
9 ms |
9044 KB |
Output is correct |
23 |
Correct |
9 ms |
9044 KB |
Output is correct |
24 |
Correct |
9 ms |
9076 KB |
Output is correct |
25 |
Correct |
9 ms |
9084 KB |
Output is correct |
26 |
Correct |
8 ms |
9016 KB |
Output is correct |
27 |
Correct |
8 ms |
9044 KB |
Output is correct |
28 |
Correct |
8 ms |
9064 KB |
Output is correct |
29 |
Correct |
9 ms |
8936 KB |
Output is correct |
30 |
Correct |
10 ms |
9076 KB |
Output is correct |
31 |
Correct |
9 ms |
9044 KB |
Output is correct |
32 |
Correct |
10 ms |
9004 KB |
Output is correct |
33 |
Correct |
9 ms |
9124 KB |
Output is correct |
34 |
Correct |
10 ms |
9060 KB |
Output is correct |
35 |
Correct |
11 ms |
9044 KB |
Output is correct |
36 |
Correct |
4 ms |
8148 KB |
Output is correct |
37 |
Correct |
9 ms |
9008 KB |
Output is correct |
38 |
Correct |
10 ms |
9068 KB |
Output is correct |
39 |
Correct |
9 ms |
9044 KB |
Output is correct |
40 |
Correct |
565 ms |
48784 KB |
Output is correct |
41 |
Correct |
650 ms |
48564 KB |
Output is correct |
42 |
Correct |
734 ms |
49928 KB |
Output is correct |
43 |
Correct |
664 ms |
45416 KB |
Output is correct |
44 |
Correct |
649 ms |
44748 KB |
Output is correct |
45 |
Correct |
1132 ms |
57828 KB |
Output is correct |
46 |
Correct |
1062 ms |
57588 KB |
Output is correct |
47 |
Correct |
1122 ms |
57548 KB |
Output is correct |
48 |
Correct |
1072 ms |
57820 KB |
Output is correct |
49 |
Correct |
1016 ms |
57700 KB |
Output is correct |
50 |
Correct |
1610 ms |
62264 KB |
Output is correct |
51 |
Correct |
1425 ms |
62692 KB |
Output is correct |
52 |
Correct |
1583 ms |
61964 KB |
Output is correct |
53 |
Correct |
1443 ms |
57656 KB |
Output is correct |
54 |
Correct |
1606 ms |
58012 KB |
Output is correct |
55 |
Correct |
1438 ms |
58008 KB |
Output is correct |
56 |
Correct |
707 ms |
58144 KB |
Output is correct |
57 |
Correct |
700 ms |
58160 KB |
Output is correct |
58 |
Correct |
712 ms |
58348 KB |
Output is correct |
59 |
Correct |
691 ms |
58172 KB |
Output is correct |
60 |
Correct |
743 ms |
57368 KB |
Output is correct |
61 |
Correct |
726 ms |
57172 KB |
Output is correct |
62 |
Correct |
764 ms |
57664 KB |
Output is correct |
63 |
Correct |
349 ms |
56908 KB |
Output is correct |
64 |
Correct |
330 ms |
55292 KB |
Output is correct |
65 |
Correct |
414 ms |
55884 KB |
Output is correct |
66 |
Correct |
419 ms |
55220 KB |
Output is correct |
67 |
Correct |
4 ms |
8160 KB |
Output is correct |
68 |
Correct |
8 ms |
9172 KB |
Output is correct |
69 |
Correct |
9 ms |
9044 KB |
Output is correct |
70 |
Correct |
9 ms |
9064 KB |
Output is correct |
71 |
Correct |
683 ms |
51772 KB |
Output is correct |
72 |
Correct |
664 ms |
51004 KB |
Output is correct |
73 |
Correct |
589 ms |
46200 KB |
Output is correct |
74 |
Correct |
1161 ms |
62696 KB |
Output is correct |
75 |
Correct |
1112 ms |
62832 KB |
Output is correct |
76 |
Correct |
1158 ms |
62748 KB |
Output is correct |
77 |
Correct |
677 ms |
62664 KB |
Output is correct |
78 |
Correct |
636 ms |
62696 KB |
Output is correct |
79 |
Correct |
665 ms |
62616 KB |
Output is correct |
80 |
Correct |
268 ms |
62476 KB |
Output is correct |
81 |
Correct |
255 ms |
62384 KB |
Output is correct |
82 |
Correct |
438 ms |
62768 KB |
Output is correct |
83 |
Correct |
432 ms |
62620 KB |
Output is correct |
84 |
Correct |
620 ms |
45612 KB |
Output is correct |
85 |
Correct |
486 ms |
40764 KB |
Output is correct |
86 |
Correct |
427 ms |
39492 KB |
Output is correct |
87 |
Correct |
972 ms |
57680 KB |
Output is correct |
88 |
Correct |
975 ms |
57820 KB |
Output is correct |
89 |
Correct |
937 ms |
57704 KB |
Output is correct |
90 |
Correct |
949 ms |
57804 KB |
Output is correct |
91 |
Correct |
984 ms |
57880 KB |
Output is correct |
92 |
Correct |
1624 ms |
60896 KB |
Output is correct |
93 |
Correct |
1532 ms |
61860 KB |
Output is correct |
94 |
Correct |
1421 ms |
57884 KB |
Output is correct |
95 |
Correct |
1424 ms |
57852 KB |
Output is correct |
96 |
Correct |
1345 ms |
57936 KB |
Output is correct |
97 |
Correct |
1314 ms |
57696 KB |
Output is correct |
98 |
Correct |
727 ms |
57804 KB |
Output is correct |
99 |
Correct |
758 ms |
57640 KB |
Output is correct |
100 |
Correct |
752 ms |
57916 KB |
Output is correct |
101 |
Correct |
729 ms |
57888 KB |
Output is correct |
102 |
Correct |
720 ms |
58192 KB |
Output is correct |
103 |
Correct |
786 ms |
58284 KB |
Output is correct |
104 |
Correct |
757 ms |
58388 KB |
Output is correct |
105 |
Correct |
394 ms |
55140 KB |
Output is correct |
106 |
Correct |
358 ms |
56780 KB |
Output is correct |
107 |
Correct |
424 ms |
54912 KB |
Output is correct |
108 |
Correct |
402 ms |
54960 KB |
Output is correct |