#include <bits/stdc++.h>
#pragma GCC Optimize("unroll-loops")
#pragma GCC Optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
const int c = 450;
struct Node {
int id, region, low, high;
vector<int> children;
};
struct Region {
vector<int> ids;
vector<pair<int, int>> ranges;
int depth;
};
Node nodes[200001];
Region regions[25001];
int ans1[450][25001], ans2[25001][450], maps_to[25001];
void dfs(int node, int& id_pool) {
int id = id_pool++;
int r = nodes[node].region;
regions[r].ids.push_back(id);
regions[r].depth++;
regions[r].ranges.push_back({id_pool, regions[r].depth});
for (int i : nodes[node].children) dfs(i, id_pool);
regions[r].depth--;
regions[r].ranges.push_back({id_pool, regions[r].depth});
}
inline int query(Region a, Region b) {
// if (a.ranges.empty()) return 0;
int ans = 0, id = 0;
while (id != b.ids.size() && b.ids[id] < a.ranges[0].first) id++;
for (int i = 0; i < a.ranges.size() - 1 && id != b.ids.size(); i++) {
int pos2 = a.ranges[i + 1].first, depth = a.ranges[i].second;
int old = id;
while (id != b.ids.size() && b.ids[id] < pos2) id++;
ans += depth * (id - old);
}
return ans;
}
int main() {
int n, r, q;
scanf("%d %d %d", &n, &r, &q);
scanf("%d", &nodes[1].region);
FOR(i, 2, n + 1) {
int p;
scanf("%d %d", &p, &nodes[i].region);
nodes[p].children.push_back(i);
}
int id_pool = 1;
dfs(1, id_pool);
int cnt = 1;
FOR(i, 1, r + 1) {
if (regions[i].ids.size() > c) {
FOR(j, 1, r + 1) {
ans1[cnt][j] = query(regions[i], regions[j]);
ans2[j][cnt] = query(regions[j], regions[i]);
}
maps_to[i] = cnt++;
}
}
while (q--) {
int a, b;
scanf("%d %d", &a, &b);
if (regions[a].ids.size() > c)
printf("%d\n", ans1[maps_to[a]][b]);
else if (regions[b].ids.size() > c)
printf("%d\n", ans2[a][maps_to[b]]);
else
printf("%d\n", query(regions[a], regions[b]));
fflush(stdout);
}
return 0;
}
Compilation message
regions.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
#pragma GCC Optimize("unroll-loops")
regions.cpp:3:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
#pragma GCC Optimize("O3")
regions.cpp: In function 'int query(Region, Region)':
regions.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (id != b.ids.size() && b.ids[id] < a.ranges[0].first) id++;
~~~^~~~~~~~~~~~~~~
regions.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.ranges.size() - 1 && id != b.ids.size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:43:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.ranges.size() - 1 && id != b.ids.size(); i++) {
~~~^~~~~~~~~~~~~~~
regions.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (id != b.ids.size() && b.ids[id] < pos2) id++;
~~~^~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &r, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &nodes[1].region);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &p, &nodes[i].region);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
19064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
26 ms |
19064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
26 ms |
19104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Correct |
14 ms |
9464 KB |
Output is correct |
| 5 |
Correct |
21 ms |
9592 KB |
Output is correct |
| 6 |
Runtime error |
27 ms |
19368 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Correct |
46 ms |
9592 KB |
Output is correct |
| 8 |
Correct |
50 ms |
9720 KB |
Output is correct |
| 9 |
Correct |
65 ms |
10232 KB |
Output is correct |
| 10 |
Correct |
80 ms |
10104 KB |
Output is correct |
| 11 |
Correct |
117 ms |
10360 KB |
Output is correct |
| 12 |
Correct |
135 ms |
11172 KB |
Output is correct |
| 13 |
Correct |
188 ms |
10792 KB |
Output is correct |
| 14 |
Correct |
175 ms |
11512 KB |
Output is correct |
| 15 |
Correct |
249 ms |
15236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1164 ms |
15936 KB |
Output is correct |
| 2 |
Correct |
1270 ms |
14404 KB |
Output is correct |
| 3 |
Correct |
1961 ms |
18412 KB |
Output is correct |
| 4 |
Runtime error |
45 ms |
23032 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
52 ms |
27640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
59 ms |
25592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
70 ms |
28280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
169 ms |
73904 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
136 ms |
41872 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
146 ms |
54428 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
155 ms |
39928 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
161 ms |
42864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
156 ms |
44208 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
198 ms |
42592 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
1534 ms |
97968 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
198 ms |
74676 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
175 ms |
70032 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
