/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 3e5 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m, q;
vector<int> G[maxn];
struct ask
{
int s, t, x, y;
} que[maxn];
int p[maxn];
int c[maxn];
struct cp
{
int p, c;
bool operator<(const cp &x)
{
return c < x.c;
}
} ch[maxn];
struct BIT
{
ll bit[maxn];
void init()
{
memset(bit, 0, sizeof(bit));
}
void upd(int id, ll val)
{
for (id; id <= n; id += id & -id)
{
bit[id] += val;
}
}
ll get(int id)
{
ll res = 0;
for (id; id >= 1; id -= id & -id)
{
res += bit[id];
}
return res;
}
} A, B;
int tin[maxn];
int tout[maxn];
int s = 0;
int par[maxn];
pair<int, int> rmq[maxn][20];
int eu1[maxn];
int tin1[maxn];
int tout1[maxn];
int s1 = 0;
void dfs(int u, int pa)
{
tin[u] = ++s;
tin1[u] = ++s1;
eu1[s1] = u;
for (auto v : G[u])
{
if (v == pa)
continue;
par[v] = u;
dfs(v, u);
eu1[++s1] = u;
}
tout[u] = s;
}
void init()
{
for (int i = 1; i <= s1; i++)
{
rmq[i][0] = {tin1[eu1[i]], eu1[i]};
}
for (int i = 1; (1 << i) <= s1; i++)
{
for (int j = 1; j + (1 << i) - 1 <= s1; j++)
{
rmq[j][i] = min(rmq[j + (1 << (i - 1))][i - 1], rmq[j][i - 1]);
}
}
}
int LCA(int u, int v)
{
if (tin1[u] > tin1[v])
swap(u, v);
int dis = 31 - __builtin_clz(tin1[v] - tin1[u] + 1);
return min(rmq[tin1[u]][dis], rmq[tin1[v] - (1 << dis) + 1][dis]).se;
}
int l[maxn];
int ans[maxn];
int r[maxn];
pair<int, int> ed[maxn];
vector<int> K[maxn];
void solve()
{
cin >> n >> m >> q;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
ed[i].fi = a;
ed[i].se = b;
G[a].pb(b);
G[b].pb(a);
}
dfs(1, -1);
init();
for (int i = 1; i <= m; i++)
{
cin >> ch[i].p >> ch[i].c;
if (par[ed[ch[i].p].fi] == ed[ch[i].p].se)
{
ch[i].p = ed[ch[i].p].fi;
}
else
{
ch[i].p = ed[ch[i].p].se;
}
}
sort(ch + 1, ch + 1 + m);
for (int i = 1; i <= q; i++)
{
cin >> que[i].s >> que[i].t >> que[i].x >> que[i].y;
ans[i] = 1e9;
l[i] = 0;
r[i] = m;
}
for (int _ = 1; _ <= 18; _++)
{
for (int i = 1; i <= q; i++)
{
if (l[i] <= r[i])
{
int mid = (l[i] + r[i]) >> 1;
K[mid].pb(i);
}
}
A.init();
B.init();
for (int i = 1; i <= m; i++)
{
A.upd(tin[ch[i].p], 1);
A.upd(tout[ch[i].p] + 1, -1);
}
for (int i = 0; i <= m; i++)
{
if (i)
{
B.upd(tin[ch[i].p], ch[i].c);
B.upd(tout[ch[i].p] + 1, -ch[i].c);
// cout << tin[ch[i].p] << " " << tout[ch[i].p] << " " << ch[i].c << "\n";
A.upd(tin[ch[i].p], -1);
A.upd(tout[ch[i].p] + 1, 1);
}
for (auto v : K[i])
{
int u = LCA(que[v].s, que[v].t);
int silver = B.get(tin[que[v].s]) + B.get(tin[que[v].t]) - 2 * B.get(tin[u]);
// cout << que[v].s << " " << que[v].t << " " << u << "\n";
int gold = A.get(tin[que[v].s]) + A.get(tin[que[v].t]) - 2 * A.get(tin[u]);
if (silver <= que[v].y)
{
ans[v] = gold;
l[v] = i + 1;
}
else
{
r[v] = i - 1;
}
}
K[i].clear();
}
}
for (int i = 1; i <= q; i++)
{
if (ans[i] <= que[i].x)
{
cout << que[i].x - ans[i] << "\n";
}
else
{
cout << "-1\n";
}
}
}
signed main()
{
cin.tie(0), cout.tie(0)->sync_with_stdio(0);
solve();
}
Compilation message
currencies.cpp: In member function 'void BIT::upd(long long int, ll)':
currencies.cpp:59:14: warning: statement has no effect [-Wunused-value]
59 | for (id; id <= n; id += id & -id)
| ^~
currencies.cpp: In member function 'll BIT::get(long long int)':
currencies.cpp:67:14: warning: statement has no effect [-Wunused-value]
67 | for (id; id >= 1; id -= id & -id)
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
19160 KB |
Output is correct |
2 |
Correct |
12 ms |
19156 KB |
Output is correct |
3 |
Correct |
12 ms |
19204 KB |
Output is correct |
4 |
Correct |
16 ms |
19144 KB |
Output is correct |
5 |
Correct |
16 ms |
20768 KB |
Output is correct |
6 |
Correct |
20 ms |
21088 KB |
Output is correct |
7 |
Correct |
19 ms |
20564 KB |
Output is correct |
8 |
Correct |
18 ms |
21152 KB |
Output is correct |
9 |
Correct |
18 ms |
21088 KB |
Output is correct |
10 |
Correct |
18 ms |
21076 KB |
Output is correct |
11 |
Correct |
19 ms |
21164 KB |
Output is correct |
12 |
Correct |
17 ms |
21076 KB |
Output is correct |
13 |
Correct |
16 ms |
21204 KB |
Output is correct |
14 |
Correct |
21 ms |
21216 KB |
Output is correct |
15 |
Correct |
18 ms |
21068 KB |
Output is correct |
16 |
Correct |
17 ms |
21076 KB |
Output is correct |
17 |
Correct |
18 ms |
21076 KB |
Output is correct |
18 |
Correct |
17 ms |
21192 KB |
Output is correct |
19 |
Correct |
17 ms |
21084 KB |
Output is correct |
20 |
Correct |
17 ms |
21096 KB |
Output is correct |
21 |
Correct |
16 ms |
21076 KB |
Output is correct |
22 |
Correct |
16 ms |
21068 KB |
Output is correct |
23 |
Correct |
17 ms |
21068 KB |
Output is correct |
24 |
Correct |
17 ms |
21168 KB |
Output is correct |
25 |
Correct |
16 ms |
21068 KB |
Output is correct |
26 |
Correct |
16 ms |
21032 KB |
Output is correct |
27 |
Correct |
18 ms |
21116 KB |
Output is correct |
28 |
Correct |
18 ms |
21176 KB |
Output is correct |
29 |
Correct |
17 ms |
21012 KB |
Output is correct |
30 |
Correct |
20 ms |
21076 KB |
Output is correct |
31 |
Correct |
19 ms |
21124 KB |
Output is correct |
32 |
Correct |
17 ms |
21160 KB |
Output is correct |
33 |
Correct |
17 ms |
21268 KB |
Output is correct |
34 |
Correct |
16 ms |
21200 KB |
Output is correct |
35 |
Correct |
16 ms |
21176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19156 KB |
Output is correct |
2 |
Correct |
17 ms |
21076 KB |
Output is correct |
3 |
Correct |
21 ms |
21076 KB |
Output is correct |
4 |
Correct |
19 ms |
21092 KB |
Output is correct |
5 |
Correct |
723 ms |
108692 KB |
Output is correct |
6 |
Correct |
774 ms |
92956 KB |
Output is correct |
7 |
Correct |
739 ms |
101748 KB |
Output is correct |
8 |
Correct |
570 ms |
98652 KB |
Output is correct |
9 |
Correct |
596 ms |
97544 KB |
Output is correct |
10 |
Correct |
945 ms |
119164 KB |
Output is correct |
11 |
Correct |
981 ms |
119076 KB |
Output is correct |
12 |
Correct |
967 ms |
118992 KB |
Output is correct |
13 |
Correct |
978 ms |
118800 KB |
Output is correct |
14 |
Correct |
957 ms |
119336 KB |
Output is correct |
15 |
Correct |
981 ms |
124384 KB |
Output is correct |
16 |
Correct |
912 ms |
124668 KB |
Output is correct |
17 |
Correct |
853 ms |
123852 KB |
Output is correct |
18 |
Correct |
1061 ms |
118784 KB |
Output is correct |
19 |
Correct |
1006 ms |
118668 KB |
Output is correct |
20 |
Correct |
1069 ms |
118684 KB |
Output is correct |
21 |
Correct |
921 ms |
119384 KB |
Output is correct |
22 |
Correct |
882 ms |
119472 KB |
Output is correct |
23 |
Correct |
901 ms |
119596 KB |
Output is correct |
24 |
Correct |
796 ms |
119496 KB |
Output is correct |
25 |
Correct |
751 ms |
118940 KB |
Output is correct |
26 |
Correct |
740 ms |
118272 KB |
Output is correct |
27 |
Correct |
767 ms |
119508 KB |
Output is correct |
28 |
Correct |
470 ms |
117956 KB |
Output is correct |
29 |
Correct |
445 ms |
116656 KB |
Output is correct |
30 |
Correct |
551 ms |
116616 KB |
Output is correct |
31 |
Correct |
517 ms |
116488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19156 KB |
Output is correct |
2 |
Correct |
16 ms |
21184 KB |
Output is correct |
3 |
Correct |
16 ms |
21228 KB |
Output is correct |
4 |
Correct |
15 ms |
21220 KB |
Output is correct |
5 |
Correct |
494 ms |
112560 KB |
Output is correct |
6 |
Correct |
539 ms |
111820 KB |
Output is correct |
7 |
Correct |
554 ms |
87708 KB |
Output is correct |
8 |
Correct |
926 ms |
128844 KB |
Output is correct |
9 |
Correct |
879 ms |
128460 KB |
Output is correct |
10 |
Correct |
797 ms |
128708 KB |
Output is correct |
11 |
Correct |
804 ms |
128808 KB |
Output is correct |
12 |
Correct |
865 ms |
128680 KB |
Output is correct |
13 |
Correct |
775 ms |
128644 KB |
Output is correct |
14 |
Correct |
519 ms |
128224 KB |
Output is correct |
15 |
Correct |
502 ms |
128348 KB |
Output is correct |
16 |
Correct |
609 ms |
128464 KB |
Output is correct |
17 |
Correct |
626 ms |
128452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
19160 KB |
Output is correct |
2 |
Correct |
12 ms |
19156 KB |
Output is correct |
3 |
Correct |
12 ms |
19204 KB |
Output is correct |
4 |
Correct |
16 ms |
19144 KB |
Output is correct |
5 |
Correct |
16 ms |
20768 KB |
Output is correct |
6 |
Correct |
20 ms |
21088 KB |
Output is correct |
7 |
Correct |
19 ms |
20564 KB |
Output is correct |
8 |
Correct |
18 ms |
21152 KB |
Output is correct |
9 |
Correct |
18 ms |
21088 KB |
Output is correct |
10 |
Correct |
18 ms |
21076 KB |
Output is correct |
11 |
Correct |
19 ms |
21164 KB |
Output is correct |
12 |
Correct |
17 ms |
21076 KB |
Output is correct |
13 |
Correct |
16 ms |
21204 KB |
Output is correct |
14 |
Correct |
21 ms |
21216 KB |
Output is correct |
15 |
Correct |
18 ms |
21068 KB |
Output is correct |
16 |
Correct |
17 ms |
21076 KB |
Output is correct |
17 |
Correct |
18 ms |
21076 KB |
Output is correct |
18 |
Correct |
17 ms |
21192 KB |
Output is correct |
19 |
Correct |
17 ms |
21084 KB |
Output is correct |
20 |
Correct |
17 ms |
21096 KB |
Output is correct |
21 |
Correct |
16 ms |
21076 KB |
Output is correct |
22 |
Correct |
16 ms |
21068 KB |
Output is correct |
23 |
Correct |
17 ms |
21068 KB |
Output is correct |
24 |
Correct |
17 ms |
21168 KB |
Output is correct |
25 |
Correct |
16 ms |
21068 KB |
Output is correct |
26 |
Correct |
16 ms |
21032 KB |
Output is correct |
27 |
Correct |
18 ms |
21116 KB |
Output is correct |
28 |
Correct |
18 ms |
21176 KB |
Output is correct |
29 |
Correct |
17 ms |
21012 KB |
Output is correct |
30 |
Correct |
20 ms |
21076 KB |
Output is correct |
31 |
Correct |
19 ms |
21124 KB |
Output is correct |
32 |
Correct |
17 ms |
21160 KB |
Output is correct |
33 |
Correct |
17 ms |
21268 KB |
Output is correct |
34 |
Correct |
16 ms |
21200 KB |
Output is correct |
35 |
Correct |
16 ms |
21176 KB |
Output is correct |
36 |
Correct |
11 ms |
19156 KB |
Output is correct |
37 |
Correct |
17 ms |
21076 KB |
Output is correct |
38 |
Correct |
21 ms |
21076 KB |
Output is correct |
39 |
Correct |
19 ms |
21092 KB |
Output is correct |
40 |
Correct |
723 ms |
108692 KB |
Output is correct |
41 |
Correct |
774 ms |
92956 KB |
Output is correct |
42 |
Correct |
739 ms |
101748 KB |
Output is correct |
43 |
Correct |
570 ms |
98652 KB |
Output is correct |
44 |
Correct |
596 ms |
97544 KB |
Output is correct |
45 |
Correct |
945 ms |
119164 KB |
Output is correct |
46 |
Correct |
981 ms |
119076 KB |
Output is correct |
47 |
Correct |
967 ms |
118992 KB |
Output is correct |
48 |
Correct |
978 ms |
118800 KB |
Output is correct |
49 |
Correct |
957 ms |
119336 KB |
Output is correct |
50 |
Correct |
981 ms |
124384 KB |
Output is correct |
51 |
Correct |
912 ms |
124668 KB |
Output is correct |
52 |
Correct |
853 ms |
123852 KB |
Output is correct |
53 |
Correct |
1061 ms |
118784 KB |
Output is correct |
54 |
Correct |
1006 ms |
118668 KB |
Output is correct |
55 |
Correct |
1069 ms |
118684 KB |
Output is correct |
56 |
Correct |
921 ms |
119384 KB |
Output is correct |
57 |
Correct |
882 ms |
119472 KB |
Output is correct |
58 |
Correct |
901 ms |
119596 KB |
Output is correct |
59 |
Correct |
796 ms |
119496 KB |
Output is correct |
60 |
Correct |
751 ms |
118940 KB |
Output is correct |
61 |
Correct |
740 ms |
118272 KB |
Output is correct |
62 |
Correct |
767 ms |
119508 KB |
Output is correct |
63 |
Correct |
470 ms |
117956 KB |
Output is correct |
64 |
Correct |
445 ms |
116656 KB |
Output is correct |
65 |
Correct |
551 ms |
116616 KB |
Output is correct |
66 |
Correct |
517 ms |
116488 KB |
Output is correct |
67 |
Correct |
12 ms |
19156 KB |
Output is correct |
68 |
Correct |
16 ms |
21184 KB |
Output is correct |
69 |
Correct |
16 ms |
21228 KB |
Output is correct |
70 |
Correct |
15 ms |
21220 KB |
Output is correct |
71 |
Correct |
494 ms |
112560 KB |
Output is correct |
72 |
Correct |
539 ms |
111820 KB |
Output is correct |
73 |
Correct |
554 ms |
87708 KB |
Output is correct |
74 |
Correct |
926 ms |
128844 KB |
Output is correct |
75 |
Correct |
879 ms |
128460 KB |
Output is correct |
76 |
Correct |
797 ms |
128708 KB |
Output is correct |
77 |
Correct |
804 ms |
128808 KB |
Output is correct |
78 |
Correct |
865 ms |
128680 KB |
Output is correct |
79 |
Correct |
775 ms |
128644 KB |
Output is correct |
80 |
Correct |
519 ms |
128224 KB |
Output is correct |
81 |
Correct |
502 ms |
128348 KB |
Output is correct |
82 |
Correct |
609 ms |
128464 KB |
Output is correct |
83 |
Correct |
626 ms |
128452 KB |
Output is correct |
84 |
Correct |
840 ms |
100148 KB |
Output is correct |
85 |
Correct |
768 ms |
80900 KB |
Output is correct |
86 |
Correct |
659 ms |
79328 KB |
Output is correct |
87 |
Correct |
1076 ms |
122176 KB |
Output is correct |
88 |
Correct |
1147 ms |
122144 KB |
Output is correct |
89 |
Correct |
1224 ms |
122156 KB |
Output is correct |
90 |
Correct |
1079 ms |
122356 KB |
Output is correct |
91 |
Correct |
1138 ms |
122228 KB |
Output is correct |
92 |
Correct |
1078 ms |
126324 KB |
Output is correct |
93 |
Correct |
961 ms |
127508 KB |
Output is correct |
94 |
Correct |
1271 ms |
122092 KB |
Output is correct |
95 |
Correct |
1214 ms |
122316 KB |
Output is correct |
96 |
Correct |
1167 ms |
122168 KB |
Output is correct |
97 |
Correct |
1136 ms |
122228 KB |
Output is correct |
98 |
Correct |
1022 ms |
122452 KB |
Output is correct |
99 |
Correct |
1012 ms |
122052 KB |
Output is correct |
100 |
Correct |
985 ms |
122496 KB |
Output is correct |
101 |
Correct |
935 ms |
122568 KB |
Output is correct |
102 |
Correct |
933 ms |
122704 KB |
Output is correct |
103 |
Correct |
911 ms |
122644 KB |
Output is correct |
104 |
Correct |
861 ms |
122744 KB |
Output is correct |
105 |
Correct |
526 ms |
119372 KB |
Output is correct |
106 |
Correct |
510 ms |
121096 KB |
Output is correct |
107 |
Correct |
542 ms |
119292 KB |
Output is correct |
108 |
Correct |
537 ms |
119256 KB |
Output is correct |