#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5;
int n, m, q;
vector<int> g[N];
int bit[N], bit2[N];
int depth[N], tin[N], tout[N], tim = 0, dp[18][N];
vector<array<int, 2> > edges(N), checkpoints(N);
vector<array<int, 8> > queries(N);
// first 4 are queries values, next two left and right pointers for parallel binary search, second last is the answer
// last is the count of checkpoints for each query
struct BIT
{
int bit[N];
void init()
{
for(int i = 0; i < n + 5; i++)
{
bit[i] = 0;
}
}
void update(int pos, int val)
{
if(pos == 0) return;
for(int i = pos; i < n + 5; i += (i & (-i)))
{
bit[i] += val;
}
}
int query(int pos)
{
if(pos == 0) return 0;
int ans = 0;
for(int i = pos; i > 0; i -= (i & (-i)))
{
ans += bit[i];
}
return ans;
}
} cnt, value;
void dfs(int node, int par)
{
dp[0][node] = par;
tin[node] = ++tim;
for(int to: g[node])
{
if(to == par) continue;
depth[to] = depth[node] + 1;
dfs(to, node);
}
tout[node] = tim;
}
int LCA(int u, int v)
{
if(depth[u] < depth[v])
{
swap(u, v);
}
int diff = depth[u] - depth[v];
for(int i = 17; i >= 0; i--)
{
if((1 << i) & diff)
{
u = dp[i][u];
}
}
if(u == v) return u;
for(int i = 17; i >= 0; i--)
{
if(dp[i][v] != dp[i][u])
{
v = dp[i][v];
u = dp[i][u];
}
}
return dp[0][v];
}
void Solve()
{
cin >> n >> m >> q;
for(int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
edges[i] = {u, v};
}
cnt.init();
value.init();
dfs(1, -1);
// for(int i = 1; i <= n; i++)
// {
// cout << "i = " << i << ", " << tin[i] << " " << tout[i] << "\n";
// }
for(int i = 1; i < 18; i++)
{
for(int j = 1; j <= n; j++)
{
dp[i][j] = ((dp[i - 1][j] == -1) ? -1 : dp[i - 1][dp[i - 1][j]]);
}
}
for(int i = 1; i <= m; i++)
{
cin >> checkpoints[i][0] >> checkpoints[i][1];
}
sort(checkpoints.begin() + 1, checkpoints.begin() + 1 + m, [](array<int, 2> a, array<int, 2> b)
{
return a[1] < b[1];
});
for(int i = 1; i <= m; i++)
{
int edge_idx = checkpoints[i][0];
// cout << "edge_idx = " << edge_idx << endl;
int node = (depth[edges[edge_idx][0]] > depth[edges[edge_idx][1]]) ? edges[edge_idx][0] : edges[edge_idx][1];
// cout << "node = " << node << endl;
cnt.update(tin[node], 1);
cnt.update(tout[node] + 1, -1);
// cout << "update(" << tin[node] << ", 1)\n";
// cout << "update(" << tout[node] + 1 << ", -1)\n";
}
// for(int i = 1; i <= n; i++)
// {
// cout << "i = " << i << ", cnt = " << cnt.query(i) << endl;
// }
for(int i = 1; i <= q; i++)
{
cin >> queries[i][0] >> queries[i][1] >> queries[i][2] >> queries[i][3];
queries[i][4] = 0;
queries[i][5] = m;
queries[i][6] = -1;
queries[i][7] = cnt.query(tin[queries[i][0]]) + cnt.query(tin[queries[i][1]]) - 2 * cnt.query(tin[LCA(queries[i][0], queries[i][1])]);
// cout << "LCA = " << LCA(queries[i][0], queries[i][1]) << "\n";
// cout << "queries[i][7] = " << queries[i][7] << "\n";
}
while(true)
{
cnt.init();
value.init();
vector<int> queries_mid[m + 1];
int counter = 0;
for(int i = 1; i <= q; i++)
{
if(queries[i][4] > queries[i][5])
{
counter++;
continue;
}
int mid = (queries[i][4] + queries[i][5]) / 2;
// cout << "query number = " << i << ", middle value = " << mid << "\n";
queries_mid[mid].push_back(i);
}
if(counter == q)
{
break;
}
for(int i = 0; i <= m; i++)
{
for(int j = 0; j < queries_mid[i].size(); j++)
{
int index = queries_mid[i][j];
// cout << "checkpoint number = " << i << ", index = " << index << endl;
int lca = LCA(queries[index][0], queries[index][1]);
int total_value = (value.query(tin[queries[index][0]]) + value.query(tin[queries[index][1]]) - 2 * value.query(tin[lca]));
int total_count = (cnt.query(tin[queries[index][0]]) + cnt.query(tin[queries[index][1]]) - 2 * cnt.query(tin[lca]));
// cout << "total_value = " << total_value << ", total_count = " << total_count << endl;
if(total_value <= queries[index][3])
{
queries[index][6] = (queries[index][2] >= queries[index][7] - total_count) ? (queries[index][2] - (queries[index][7] - total_count)) : (-1);
queries[index][4] = i + 1;
}
else
{
queries[index][5] = i - 1;
}
}
if(i != m)
{
int edge_idx = checkpoints[i + 1][0];
int node = (depth[edges[edge_idx][0]] > depth[edges[edge_idx][1]]) ? edges[edge_idx][0] : edges[edge_idx][1];
// cout << "edge_idx = " << edge_idx << ", node = " << node << "\n";
cnt.update(tin[node], 1);
cnt.update(tout[node] + 1, -1);
value.update(tin[node], checkpoints[i + 1][1]);
value.update(tout[node] + 1, -checkpoints[i + 1][1]);
// for(int j = 1; j <= n; j++)
// {
// cout << "j = " << j << ", cnt = " << cnt.query(j) << endl;
// }
// for(int j = 1; j <= n; j++)
// {
// cout << "j = " << j << ", value = " << value.query(j) << endl;
// }
}
}
}
for(int i = 1; i <= q; i++)
{
cout << queries[i][6] << "\n";
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Compilation message
currencies.cpp: In function 'void Solve()':
currencies.cpp:169:21: 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]
169 | for(int j = 0; j < queries_mid[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
12116 KB |
Output is correct |
2 |
Correct |
5 ms |
12116 KB |
Output is correct |
3 |
Correct |
5 ms |
12116 KB |
Output is correct |
4 |
Correct |
5 ms |
12112 KB |
Output is correct |
5 |
Correct |
11 ms |
12668 KB |
Output is correct |
6 |
Correct |
12 ms |
12804 KB |
Output is correct |
7 |
Correct |
11 ms |
12620 KB |
Output is correct |
8 |
Correct |
13 ms |
12756 KB |
Output is correct |
9 |
Correct |
13 ms |
12820 KB |
Output is correct |
10 |
Correct |
14 ms |
12756 KB |
Output is correct |
11 |
Correct |
14 ms |
12756 KB |
Output is correct |
12 |
Correct |
14 ms |
12776 KB |
Output is correct |
13 |
Correct |
12 ms |
12856 KB |
Output is correct |
14 |
Correct |
12 ms |
12840 KB |
Output is correct |
15 |
Correct |
13 ms |
12812 KB |
Output is correct |
16 |
Correct |
14 ms |
12748 KB |
Output is correct |
17 |
Correct |
13 ms |
12820 KB |
Output is correct |
18 |
Correct |
13 ms |
12756 KB |
Output is correct |
19 |
Correct |
12 ms |
12756 KB |
Output is correct |
20 |
Correct |
13 ms |
12724 KB |
Output is correct |
21 |
Correct |
12 ms |
12728 KB |
Output is correct |
22 |
Correct |
12 ms |
12756 KB |
Output is correct |
23 |
Correct |
11 ms |
12756 KB |
Output is correct |
24 |
Correct |
12 ms |
12752 KB |
Output is correct |
25 |
Correct |
12 ms |
12752 KB |
Output is correct |
26 |
Correct |
10 ms |
12824 KB |
Output is correct |
27 |
Correct |
10 ms |
12756 KB |
Output is correct |
28 |
Correct |
10 ms |
12744 KB |
Output is correct |
29 |
Correct |
10 ms |
12756 KB |
Output is correct |
30 |
Correct |
14 ms |
12796 KB |
Output is correct |
31 |
Correct |
13 ms |
12820 KB |
Output is correct |
32 |
Correct |
13 ms |
12744 KB |
Output is correct |
33 |
Correct |
11 ms |
12884 KB |
Output is correct |
34 |
Correct |
11 ms |
12884 KB |
Output is correct |
35 |
Correct |
11 ms |
12876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
12116 KB |
Output is correct |
2 |
Correct |
14 ms |
12744 KB |
Output is correct |
3 |
Correct |
14 ms |
12748 KB |
Output is correct |
4 |
Correct |
13 ms |
12748 KB |
Output is correct |
5 |
Correct |
2203 ms |
41504 KB |
Output is correct |
6 |
Correct |
2001 ms |
35432 KB |
Output is correct |
7 |
Correct |
2218 ms |
37840 KB |
Output is correct |
8 |
Correct |
1899 ms |
37592 KB |
Output is correct |
9 |
Correct |
1786 ms |
37524 KB |
Output is correct |
10 |
Correct |
3471 ms |
42928 KB |
Output is correct |
11 |
Correct |
3453 ms |
43032 KB |
Output is correct |
12 |
Correct |
3531 ms |
43068 KB |
Output is correct |
13 |
Correct |
3522 ms |
43180 KB |
Output is correct |
14 |
Correct |
3558 ms |
43028 KB |
Output is correct |
15 |
Correct |
2290 ms |
45524 KB |
Output is correct |
16 |
Correct |
1954 ms |
45844 KB |
Output is correct |
17 |
Correct |
2348 ms |
45260 KB |
Output is correct |
18 |
Correct |
3490 ms |
42812 KB |
Output is correct |
19 |
Correct |
3387 ms |
42804 KB |
Output is correct |
20 |
Correct |
3091 ms |
43148 KB |
Output is correct |
21 |
Correct |
3608 ms |
42748 KB |
Output is correct |
22 |
Correct |
3375 ms |
42868 KB |
Output is correct |
23 |
Correct |
3294 ms |
42880 KB |
Output is correct |
24 |
Correct |
3793 ms |
42876 KB |
Output is correct |
25 |
Correct |
2128 ms |
43620 KB |
Output is correct |
26 |
Correct |
2595 ms |
43584 KB |
Output is correct |
27 |
Correct |
1227 ms |
43504 KB |
Output is correct |
28 |
Correct |
669 ms |
43120 KB |
Output is correct |
29 |
Correct |
515 ms |
43100 KB |
Output is correct |
30 |
Correct |
1070 ms |
43092 KB |
Output is correct |
31 |
Correct |
1113 ms |
43176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
12116 KB |
Output is correct |
2 |
Correct |
11 ms |
12884 KB |
Output is correct |
3 |
Correct |
10 ms |
12784 KB |
Output is correct |
4 |
Correct |
11 ms |
12784 KB |
Output is correct |
5 |
Correct |
947 ms |
42680 KB |
Output is correct |
6 |
Correct |
887 ms |
41828 KB |
Output is correct |
7 |
Correct |
832 ms |
33136 KB |
Output is correct |
8 |
Correct |
1742 ms |
45796 KB |
Output is correct |
9 |
Correct |
1715 ms |
45780 KB |
Output is correct |
10 |
Correct |
1692 ms |
45780 KB |
Output is correct |
11 |
Correct |
876 ms |
45764 KB |
Output is correct |
12 |
Correct |
868 ms |
45944 KB |
Output is correct |
13 |
Correct |
890 ms |
45756 KB |
Output is correct |
14 |
Correct |
433 ms |
45612 KB |
Output is correct |
15 |
Correct |
452 ms |
45424 KB |
Output is correct |
16 |
Correct |
726 ms |
45840 KB |
Output is correct |
17 |
Correct |
812 ms |
45696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
12116 KB |
Output is correct |
2 |
Correct |
5 ms |
12116 KB |
Output is correct |
3 |
Correct |
5 ms |
12116 KB |
Output is correct |
4 |
Correct |
5 ms |
12112 KB |
Output is correct |
5 |
Correct |
11 ms |
12668 KB |
Output is correct |
6 |
Correct |
12 ms |
12804 KB |
Output is correct |
7 |
Correct |
11 ms |
12620 KB |
Output is correct |
8 |
Correct |
13 ms |
12756 KB |
Output is correct |
9 |
Correct |
13 ms |
12820 KB |
Output is correct |
10 |
Correct |
14 ms |
12756 KB |
Output is correct |
11 |
Correct |
14 ms |
12756 KB |
Output is correct |
12 |
Correct |
14 ms |
12776 KB |
Output is correct |
13 |
Correct |
12 ms |
12856 KB |
Output is correct |
14 |
Correct |
12 ms |
12840 KB |
Output is correct |
15 |
Correct |
13 ms |
12812 KB |
Output is correct |
16 |
Correct |
14 ms |
12748 KB |
Output is correct |
17 |
Correct |
13 ms |
12820 KB |
Output is correct |
18 |
Correct |
13 ms |
12756 KB |
Output is correct |
19 |
Correct |
12 ms |
12756 KB |
Output is correct |
20 |
Correct |
13 ms |
12724 KB |
Output is correct |
21 |
Correct |
12 ms |
12728 KB |
Output is correct |
22 |
Correct |
12 ms |
12756 KB |
Output is correct |
23 |
Correct |
11 ms |
12756 KB |
Output is correct |
24 |
Correct |
12 ms |
12752 KB |
Output is correct |
25 |
Correct |
12 ms |
12752 KB |
Output is correct |
26 |
Correct |
10 ms |
12824 KB |
Output is correct |
27 |
Correct |
10 ms |
12756 KB |
Output is correct |
28 |
Correct |
10 ms |
12744 KB |
Output is correct |
29 |
Correct |
10 ms |
12756 KB |
Output is correct |
30 |
Correct |
14 ms |
12796 KB |
Output is correct |
31 |
Correct |
13 ms |
12820 KB |
Output is correct |
32 |
Correct |
13 ms |
12744 KB |
Output is correct |
33 |
Correct |
11 ms |
12884 KB |
Output is correct |
34 |
Correct |
11 ms |
12884 KB |
Output is correct |
35 |
Correct |
11 ms |
12876 KB |
Output is correct |
36 |
Correct |
5 ms |
12116 KB |
Output is correct |
37 |
Correct |
14 ms |
12744 KB |
Output is correct |
38 |
Correct |
14 ms |
12748 KB |
Output is correct |
39 |
Correct |
13 ms |
12748 KB |
Output is correct |
40 |
Correct |
2203 ms |
41504 KB |
Output is correct |
41 |
Correct |
2001 ms |
35432 KB |
Output is correct |
42 |
Correct |
2218 ms |
37840 KB |
Output is correct |
43 |
Correct |
1899 ms |
37592 KB |
Output is correct |
44 |
Correct |
1786 ms |
37524 KB |
Output is correct |
45 |
Correct |
3471 ms |
42928 KB |
Output is correct |
46 |
Correct |
3453 ms |
43032 KB |
Output is correct |
47 |
Correct |
3531 ms |
43068 KB |
Output is correct |
48 |
Correct |
3522 ms |
43180 KB |
Output is correct |
49 |
Correct |
3558 ms |
43028 KB |
Output is correct |
50 |
Correct |
2290 ms |
45524 KB |
Output is correct |
51 |
Correct |
1954 ms |
45844 KB |
Output is correct |
52 |
Correct |
2348 ms |
45260 KB |
Output is correct |
53 |
Correct |
3490 ms |
42812 KB |
Output is correct |
54 |
Correct |
3387 ms |
42804 KB |
Output is correct |
55 |
Correct |
3091 ms |
43148 KB |
Output is correct |
56 |
Correct |
3608 ms |
42748 KB |
Output is correct |
57 |
Correct |
3375 ms |
42868 KB |
Output is correct |
58 |
Correct |
3294 ms |
42880 KB |
Output is correct |
59 |
Correct |
3793 ms |
42876 KB |
Output is correct |
60 |
Correct |
2128 ms |
43620 KB |
Output is correct |
61 |
Correct |
2595 ms |
43584 KB |
Output is correct |
62 |
Correct |
1227 ms |
43504 KB |
Output is correct |
63 |
Correct |
669 ms |
43120 KB |
Output is correct |
64 |
Correct |
515 ms |
43100 KB |
Output is correct |
65 |
Correct |
1070 ms |
43092 KB |
Output is correct |
66 |
Correct |
1113 ms |
43176 KB |
Output is correct |
67 |
Correct |
5 ms |
12116 KB |
Output is correct |
68 |
Correct |
11 ms |
12884 KB |
Output is correct |
69 |
Correct |
10 ms |
12784 KB |
Output is correct |
70 |
Correct |
11 ms |
12784 KB |
Output is correct |
71 |
Correct |
947 ms |
42680 KB |
Output is correct |
72 |
Correct |
887 ms |
41828 KB |
Output is correct |
73 |
Correct |
832 ms |
33136 KB |
Output is correct |
74 |
Correct |
1742 ms |
45796 KB |
Output is correct |
75 |
Correct |
1715 ms |
45780 KB |
Output is correct |
76 |
Correct |
1692 ms |
45780 KB |
Output is correct |
77 |
Correct |
876 ms |
45764 KB |
Output is correct |
78 |
Correct |
868 ms |
45944 KB |
Output is correct |
79 |
Correct |
890 ms |
45756 KB |
Output is correct |
80 |
Correct |
433 ms |
45612 KB |
Output is correct |
81 |
Correct |
452 ms |
45424 KB |
Output is correct |
82 |
Correct |
726 ms |
45840 KB |
Output is correct |
83 |
Correct |
812 ms |
45696 KB |
Output is correct |
84 |
Correct |
1930 ms |
38160 KB |
Output is correct |
85 |
Correct |
1164 ms |
31424 KB |
Output is correct |
86 |
Correct |
1287 ms |
30308 KB |
Output is correct |
87 |
Correct |
3386 ms |
43032 KB |
Output is correct |
88 |
Correct |
3487 ms |
43028 KB |
Output is correct |
89 |
Correct |
3393 ms |
43004 KB |
Output is correct |
90 |
Correct |
3579 ms |
43032 KB |
Output is correct |
91 |
Correct |
3369 ms |
42972 KB |
Output is correct |
92 |
Correct |
2439 ms |
43980 KB |
Output is correct |
93 |
Correct |
2278 ms |
45096 KB |
Output is correct |
94 |
Correct |
3170 ms |
43048 KB |
Output is correct |
95 |
Correct |
3468 ms |
42856 KB |
Output is correct |
96 |
Correct |
3218 ms |
43000 KB |
Output is correct |
97 |
Correct |
3331 ms |
43000 KB |
Output is correct |
98 |
Correct |
4019 ms |
42896 KB |
Output is correct |
99 |
Correct |
3624 ms |
42756 KB |
Output is correct |
100 |
Correct |
3848 ms |
43044 KB |
Output is correct |
101 |
Correct |
3765 ms |
42924 KB |
Output is correct |
102 |
Correct |
2053 ms |
43540 KB |
Output is correct |
103 |
Correct |
2441 ms |
43632 KB |
Output is correct |
104 |
Correct |
2553 ms |
43624 KB |
Output is correct |
105 |
Correct |
699 ms |
43060 KB |
Output is correct |
106 |
Correct |
657 ms |
43236 KB |
Output is correct |
107 |
Correct |
1042 ms |
42796 KB |
Output is correct |
108 |
Correct |
1109 ms |
42780 KB |
Output is correct |