#include <cstdio>
#include <vector>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair<int, ll> pil;
const int LOG = 17;
const int N = 1 << LOG;
struct node {
node *l, *r;
int cnt;
ll upd;
node() : l(NULL), r(NULL), cnt(0), upd(0) {}
node(node *l, node *r, int cnt, ll upd) : l(l), r(r), cnt(cnt), upd(upd) {}
};
typedef node* pnode;
int GET;
node T[3 * LOG * N];
pnode get(pnode u = NULL) {
if(u != NULL) {
T[GET].l = u->l;
T[GET].r = u->r;
T[GET].cnt = u->cnt;
T[GET].upd = u->upd;
}
return &T[GET++];
}
pnode update(int l, int r, ll val, pnode u = NULL, int lo = 0, int hi = N) {
if(r <= lo || hi <= l) return u;
if(l <= lo && hi <= r) {
pnode v = get(u);
v->cnt += 1;
v->upd += val;
return v;
}
pnode v = get(u);
int mi = (lo + hi) / 2;
if(u->l == NULL) u->l = get();
if(u->r == NULL) u->r = get();
v->l = update(l, r, val, u->l, lo, mi);
v->r = update(l, r, val, u->r, mi, hi);
return v;
}
int IV[N], MR[N], mrv;
int UP[N][LOG], DEP[N];
vector<int> G[N];
pil query(int x, pnode u, int lo = 0, int hi = N) {
if(u == NULL) return {0, 0};
if(lo + 1 == hi) return {u->cnt, u->upd};
int mi = (lo + hi) / 2;
pil res = IV[x] < mi ? query(x, u->l, lo, mi) : query(x, u->r, mi, hi);
return {res.X + u->cnt, res.Y + u->upd};
}
void dfs(int u, int p) { // DEP[1] = 1 !!!
IV[u] = mrv++;
for(int v : G[u])
if(v != p) {
DEP[v] = DEP[u] + 1;
UP[v][0] = u;
dfs(v, u);
}
MR[u] = mrv;
}
int lca(int u, int v) {
if(DEP[u] > DEP[v]) swap(u, v);
for(int i = LOG - 1; i >= 0; --i)
if(DEP[UP[v][i]] >= DEP[u]) v = UP[v][i];
if(u == v) return u;
for(int i = LOG - 1; i >= 0; --i)
if(UP[u][i] != UP[v][i]) {
u = UP[u][i];
v = UP[v][i];
}
return UP[u][0];
}
int A[N], B[N], P[N], C[N];
int I[N];
pnode RT[N];
pil query_path(int u, int v, int anc, int t) {
pil ru = query(u, RT[t]), rv = query(v, RT[t]), ranc = query(anc, RT[t]);
// if(u == 4 && v == 6) printf(">>> %d %d %lld\n", t, ranc.X, ranc.Y);
return {ru.X + rv.X - 2 * ranc.X, ru.Y + rv.Y - 2 * ranc.Y};
}
int main() {
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for(int i = 0; i < n - 1; ++i) {
scanf("%d%d", A + i, B + i);
G[A[i]].PB(B[i]);
G[B[i]].PB(A[i]);
}
for(int i = 1; i <= m; ++i) {
I[i] = i;
scanf("%d%d", P + i, C + i);
--P[i];
}
sort(I + 1, I + m + 1, [&](int a, int b) { return C[a] < C[b]; });
DEP[1] = 1;
dfs(1, 0);
for(int i = 1; i < LOG; ++i)
for(int j = 1; j <= n; ++j) UP[j][i] = UP[UP[j][i - 1]][i - 1];
RT[0] = get();
for(int i = 1; i <= m; ++i) {
int ind = I[i], p = P[ind], u = (DEP[A[p]] < DEP[B[p]] ? B[p] : A[p]);
RT[i] = update(IV[u], MR[u], C[ind], RT[i - 1]);
// printf("! %d[%d, %d] + %d\n", u, IV[u], MR[u], C[ind]);
}
for(; q--; ) {
int s, t, x;
ll y;
scanf("%d%d%d%lld", &s, &t, &x, &y);
int a = lca(s, t), lo = -1, hi = m + 1;
for(; hi - lo > 1; ) {
int mi = (lo + hi) / 2;
pil res = query_path(s, t, a, mi);
// if(q == 6) printf("%d: %d %lld\n", mi, res.X, res.Y);
if(res.Y > y) hi = mi;
else lo = mi;
}
pil res = query_path(s, t, a, lo), res_ = query_path(s, t, a, m);
// printf("%d %d %d | %d\n", s, t, a, lo);
printf("%d\n", max(-1, x - (res_.X - res.X)));
}
return 0;
}
Compilation message
currencies.cpp: In function 'int main()':
currencies.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | scanf("%d%d%d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | scanf("%d%d", A + i, B + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | scanf("%d%d", P + i, C + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
135 | scanf("%d%d%d%lld", &s, &t, &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
140 ms |
214272 KB |
Output is correct |
2 |
Correct |
58 ms |
214352 KB |
Output is correct |
3 |
Correct |
59 ms |
214240 KB |
Output is correct |
4 |
Correct |
57 ms |
214356 KB |
Output is correct |
5 |
Correct |
62 ms |
214672 KB |
Output is correct |
6 |
Correct |
66 ms |
214684 KB |
Output is correct |
7 |
Correct |
66 ms |
215376 KB |
Output is correct |
8 |
Correct |
64 ms |
214864 KB |
Output is correct |
9 |
Correct |
64 ms |
214716 KB |
Output is correct |
10 |
Correct |
67 ms |
214612 KB |
Output is correct |
11 |
Correct |
63 ms |
214616 KB |
Output is correct |
12 |
Correct |
62 ms |
214468 KB |
Output is correct |
13 |
Correct |
66 ms |
214656 KB |
Output is correct |
14 |
Correct |
66 ms |
214592 KB |
Output is correct |
15 |
Correct |
63 ms |
214628 KB |
Output is correct |
16 |
Correct |
62 ms |
214536 KB |
Output is correct |
17 |
Correct |
64 ms |
214612 KB |
Output is correct |
18 |
Correct |
66 ms |
214660 KB |
Output is correct |
19 |
Correct |
61 ms |
214612 KB |
Output is correct |
20 |
Correct |
58 ms |
214768 KB |
Output is correct |
21 |
Correct |
49 ms |
214612 KB |
Output is correct |
22 |
Correct |
47 ms |
214608 KB |
Output is correct |
23 |
Correct |
45 ms |
214616 KB |
Output is correct |
24 |
Correct |
44 ms |
214632 KB |
Output is correct |
25 |
Correct |
46 ms |
214604 KB |
Output is correct |
26 |
Correct |
45 ms |
214620 KB |
Output is correct |
27 |
Correct |
44 ms |
214660 KB |
Output is correct |
28 |
Correct |
43 ms |
214608 KB |
Output is correct |
29 |
Correct |
42 ms |
214612 KB |
Output is correct |
30 |
Correct |
44 ms |
214612 KB |
Output is correct |
31 |
Correct |
43 ms |
214616 KB |
Output is correct |
32 |
Correct |
44 ms |
214616 KB |
Output is correct |
33 |
Correct |
44 ms |
214852 KB |
Output is correct |
34 |
Correct |
44 ms |
214616 KB |
Output is correct |
35 |
Correct |
44 ms |
214648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
214352 KB |
Output is correct |
2 |
Correct |
44 ms |
214628 KB |
Output is correct |
3 |
Correct |
43 ms |
214612 KB |
Output is correct |
4 |
Correct |
43 ms |
214508 KB |
Output is correct |
5 |
Correct |
904 ms |
231776 KB |
Output is correct |
6 |
Correct |
1265 ms |
228612 KB |
Output is correct |
7 |
Correct |
1036 ms |
230012 KB |
Output is correct |
8 |
Correct |
741 ms |
229368 KB |
Output is correct |
9 |
Correct |
726 ms |
229452 KB |
Output is correct |
10 |
Correct |
1606 ms |
233120 KB |
Output is correct |
11 |
Correct |
1520 ms |
232860 KB |
Output is correct |
12 |
Correct |
1556 ms |
232856 KB |
Output is correct |
13 |
Correct |
1542 ms |
233276 KB |
Output is correct |
14 |
Correct |
1430 ms |
232884 KB |
Output is correct |
15 |
Correct |
1903 ms |
239032 KB |
Output is correct |
16 |
Correct |
1962 ms |
239832 KB |
Output is correct |
17 |
Correct |
1968 ms |
239164 KB |
Output is correct |
18 |
Correct |
1940 ms |
233224 KB |
Output is correct |
19 |
Correct |
1899 ms |
233240 KB |
Output is correct |
20 |
Correct |
1858 ms |
233388 KB |
Output is correct |
21 |
Correct |
1288 ms |
232436 KB |
Output is correct |
22 |
Correct |
1367 ms |
232696 KB |
Output is correct |
23 |
Correct |
1253 ms |
232388 KB |
Output is correct |
24 |
Correct |
1253 ms |
232524 KB |
Output is correct |
25 |
Correct |
1069 ms |
233040 KB |
Output is correct |
26 |
Correct |
1006 ms |
233208 KB |
Output is correct |
27 |
Correct |
1065 ms |
233168 KB |
Output is correct |
28 |
Correct |
470 ms |
232460 KB |
Output is correct |
29 |
Correct |
505 ms |
232480 KB |
Output is correct |
30 |
Correct |
624 ms |
232732 KB |
Output is correct |
31 |
Correct |
639 ms |
232776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
214356 KB |
Output is correct |
2 |
Correct |
46 ms |
215188 KB |
Output is correct |
3 |
Correct |
44 ms |
214844 KB |
Output is correct |
4 |
Correct |
44 ms |
214612 KB |
Output is correct |
5 |
Correct |
950 ms |
236876 KB |
Output is correct |
6 |
Correct |
897 ms |
235712 KB |
Output is correct |
7 |
Correct |
1327 ms |
231140 KB |
Output is correct |
8 |
Correct |
1822 ms |
239764 KB |
Output is correct |
9 |
Correct |
1837 ms |
239796 KB |
Output is correct |
10 |
Correct |
1839 ms |
239636 KB |
Output is correct |
11 |
Correct |
1327 ms |
239724 KB |
Output is correct |
12 |
Correct |
1295 ms |
239700 KB |
Output is correct |
13 |
Correct |
1359 ms |
239588 KB |
Output is correct |
14 |
Correct |
701 ms |
239992 KB |
Output is correct |
15 |
Correct |
655 ms |
239752 KB |
Output is correct |
16 |
Correct |
935 ms |
239684 KB |
Output is correct |
17 |
Correct |
954 ms |
239688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
140 ms |
214272 KB |
Output is correct |
2 |
Correct |
58 ms |
214352 KB |
Output is correct |
3 |
Correct |
59 ms |
214240 KB |
Output is correct |
4 |
Correct |
57 ms |
214356 KB |
Output is correct |
5 |
Correct |
62 ms |
214672 KB |
Output is correct |
6 |
Correct |
66 ms |
214684 KB |
Output is correct |
7 |
Correct |
66 ms |
215376 KB |
Output is correct |
8 |
Correct |
64 ms |
214864 KB |
Output is correct |
9 |
Correct |
64 ms |
214716 KB |
Output is correct |
10 |
Correct |
67 ms |
214612 KB |
Output is correct |
11 |
Correct |
63 ms |
214616 KB |
Output is correct |
12 |
Correct |
62 ms |
214468 KB |
Output is correct |
13 |
Correct |
66 ms |
214656 KB |
Output is correct |
14 |
Correct |
66 ms |
214592 KB |
Output is correct |
15 |
Correct |
63 ms |
214628 KB |
Output is correct |
16 |
Correct |
62 ms |
214536 KB |
Output is correct |
17 |
Correct |
64 ms |
214612 KB |
Output is correct |
18 |
Correct |
66 ms |
214660 KB |
Output is correct |
19 |
Correct |
61 ms |
214612 KB |
Output is correct |
20 |
Correct |
58 ms |
214768 KB |
Output is correct |
21 |
Correct |
49 ms |
214612 KB |
Output is correct |
22 |
Correct |
47 ms |
214608 KB |
Output is correct |
23 |
Correct |
45 ms |
214616 KB |
Output is correct |
24 |
Correct |
44 ms |
214632 KB |
Output is correct |
25 |
Correct |
46 ms |
214604 KB |
Output is correct |
26 |
Correct |
45 ms |
214620 KB |
Output is correct |
27 |
Correct |
44 ms |
214660 KB |
Output is correct |
28 |
Correct |
43 ms |
214608 KB |
Output is correct |
29 |
Correct |
42 ms |
214612 KB |
Output is correct |
30 |
Correct |
44 ms |
214612 KB |
Output is correct |
31 |
Correct |
43 ms |
214616 KB |
Output is correct |
32 |
Correct |
44 ms |
214616 KB |
Output is correct |
33 |
Correct |
44 ms |
214852 KB |
Output is correct |
34 |
Correct |
44 ms |
214616 KB |
Output is correct |
35 |
Correct |
44 ms |
214648 KB |
Output is correct |
36 |
Correct |
39 ms |
214352 KB |
Output is correct |
37 |
Correct |
44 ms |
214628 KB |
Output is correct |
38 |
Correct |
43 ms |
214612 KB |
Output is correct |
39 |
Correct |
43 ms |
214508 KB |
Output is correct |
40 |
Correct |
904 ms |
231776 KB |
Output is correct |
41 |
Correct |
1265 ms |
228612 KB |
Output is correct |
42 |
Correct |
1036 ms |
230012 KB |
Output is correct |
43 |
Correct |
741 ms |
229368 KB |
Output is correct |
44 |
Correct |
726 ms |
229452 KB |
Output is correct |
45 |
Correct |
1606 ms |
233120 KB |
Output is correct |
46 |
Correct |
1520 ms |
232860 KB |
Output is correct |
47 |
Correct |
1556 ms |
232856 KB |
Output is correct |
48 |
Correct |
1542 ms |
233276 KB |
Output is correct |
49 |
Correct |
1430 ms |
232884 KB |
Output is correct |
50 |
Correct |
1903 ms |
239032 KB |
Output is correct |
51 |
Correct |
1962 ms |
239832 KB |
Output is correct |
52 |
Correct |
1968 ms |
239164 KB |
Output is correct |
53 |
Correct |
1940 ms |
233224 KB |
Output is correct |
54 |
Correct |
1899 ms |
233240 KB |
Output is correct |
55 |
Correct |
1858 ms |
233388 KB |
Output is correct |
56 |
Correct |
1288 ms |
232436 KB |
Output is correct |
57 |
Correct |
1367 ms |
232696 KB |
Output is correct |
58 |
Correct |
1253 ms |
232388 KB |
Output is correct |
59 |
Correct |
1253 ms |
232524 KB |
Output is correct |
60 |
Correct |
1069 ms |
233040 KB |
Output is correct |
61 |
Correct |
1006 ms |
233208 KB |
Output is correct |
62 |
Correct |
1065 ms |
233168 KB |
Output is correct |
63 |
Correct |
470 ms |
232460 KB |
Output is correct |
64 |
Correct |
505 ms |
232480 KB |
Output is correct |
65 |
Correct |
624 ms |
232732 KB |
Output is correct |
66 |
Correct |
639 ms |
232776 KB |
Output is correct |
67 |
Correct |
36 ms |
214356 KB |
Output is correct |
68 |
Correct |
46 ms |
215188 KB |
Output is correct |
69 |
Correct |
44 ms |
214844 KB |
Output is correct |
70 |
Correct |
44 ms |
214612 KB |
Output is correct |
71 |
Correct |
950 ms |
236876 KB |
Output is correct |
72 |
Correct |
897 ms |
235712 KB |
Output is correct |
73 |
Correct |
1327 ms |
231140 KB |
Output is correct |
74 |
Correct |
1822 ms |
239764 KB |
Output is correct |
75 |
Correct |
1837 ms |
239796 KB |
Output is correct |
76 |
Correct |
1839 ms |
239636 KB |
Output is correct |
77 |
Correct |
1327 ms |
239724 KB |
Output is correct |
78 |
Correct |
1295 ms |
239700 KB |
Output is correct |
79 |
Correct |
1359 ms |
239588 KB |
Output is correct |
80 |
Correct |
701 ms |
239992 KB |
Output is correct |
81 |
Correct |
655 ms |
239752 KB |
Output is correct |
82 |
Correct |
935 ms |
239684 KB |
Output is correct |
83 |
Correct |
954 ms |
239688 KB |
Output is correct |
84 |
Correct |
854 ms |
229980 KB |
Output is correct |
85 |
Correct |
900 ms |
226464 KB |
Output is correct |
86 |
Correct |
861 ms |
225364 KB |
Output is correct |
87 |
Correct |
1504 ms |
232876 KB |
Output is correct |
88 |
Correct |
1450 ms |
232980 KB |
Output is correct |
89 |
Correct |
1466 ms |
232744 KB |
Output is correct |
90 |
Correct |
1615 ms |
233028 KB |
Output is correct |
91 |
Correct |
1479 ms |
232856 KB |
Output is correct |
92 |
Correct |
1965 ms |
237556 KB |
Output is correct |
93 |
Correct |
1932 ms |
238528 KB |
Output is correct |
94 |
Correct |
1942 ms |
233192 KB |
Output is correct |
95 |
Correct |
1835 ms |
233036 KB |
Output is correct |
96 |
Correct |
1899 ms |
233744 KB |
Output is correct |
97 |
Correct |
1810 ms |
233564 KB |
Output is correct |
98 |
Correct |
1279 ms |
232848 KB |
Output is correct |
99 |
Correct |
1302 ms |
232884 KB |
Output is correct |
100 |
Correct |
1268 ms |
232680 KB |
Output is correct |
101 |
Correct |
1296 ms |
232788 KB |
Output is correct |
102 |
Correct |
1048 ms |
233228 KB |
Output is correct |
103 |
Correct |
1114 ms |
233308 KB |
Output is correct |
104 |
Correct |
1074 ms |
233184 KB |
Output is correct |
105 |
Correct |
506 ms |
232700 KB |
Output is correct |
106 |
Correct |
494 ms |
232784 KB |
Output is correct |
107 |
Correct |
662 ms |
232544 KB |
Output is correct |
108 |
Correct |
639 ms |
232692 KB |
Output is correct |