#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int maxn = 1e5 * 2 + 10;
const int maxr = 25000 + 10;
int visit[maxn], finish[maxn], region[maxn];
vector <int> adj[maxn];
vector <int> region_members[maxr];
int big_region_id[maxr];
vector <int> r1r2[maxr];
vector <int> cnt_parents[maxn];
int t = 0;
void dfs(int s) {
visit[s] = t++;
for (int i = 0; i < adj[s].size(); i++)
dfs(adj[s][i]);
finish[s] = t++;
}
int big_region_cnt = 0;
void dfs2(int s, int p) {
int id1 = big_region_id[region[s]];
int id2 = big_region_id[region[p]];
cnt_parents[s] = cnt_parents[p];
if (id2 != -1)
cnt_parents[s][id2]++;
if (id1 != -1) {
for (int i = 0; i < big_region_cnt; i++)
r1r2[i][id1] += cnt_parents[s][i];
}
for (int i = 0; i < adj[s].size(); i++)
dfs2(adj[s][i], s);
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int n, r, q;
cin >> n >> r >> q;
cin >> region[1];
region_members[region[1]].push_back(1);
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
adj[x].push_back(i);
cin >> region[i];
region_members[region[i]].push_back(i);
}
fill(big_region_id, big_region_id + maxr, -1);
for (int i = 1; i <= r; i++) {
if (region_members[i].size() > 500)
big_region_id[i] = big_region_cnt++;
}
for (int i = 1; i <= n; i++) {
cnt_parents[i].resize(big_region_cnt);
if (i <= big_region_cnt)
r1r2[i].resize(big_region_cnt);
}
dfs(1);
vector <vector <int>> starts(r+1);
for (int i = 1; i <= r; i++) {
for (int j = 0; j < region_members[i].size(); j++)
starts[i].push_back(visit[region_members[i][j]]);
sort(starts[i].begin(), starts[i].end());
}
dfs2(1, 1);
while (q--) {
int r1, r2;
cin >> r1 >> r2;
if (big_region_id[r1] == -1) { // r1 = small
int ans = 0;
vector <int> &st = starts[r2];
for (int i = 0; i < region_members[r1].size(); i++) {
auto l = upper_bound(st.begin(), st.end(), visit[region_members[r1][i]]);
auto r = upper_bound(st.begin(), st.end(), finish[region_members[r1][i]]);
if (r == st.begin())
continue;
r--;
int id1 = l - st.begin();
int id2 = r - st.begin();
ans += max(0, (id2 - id1 + 1));
}
cout << ans << endl;
} else if (big_region_id[r2] != -1) { // r2 = big
int a = big_region_id[r1];
int b = big_region_id[r2];
cout << r1r2[a][b] << endl;
} else { // r1 = big, r2 = small
int ans = 0;
for (int i = 0; i < region_members[r2].size(); i++)
ans += cnt_parents[region_members[r2][i]][big_region_id[r1]];
cout << ans << endl;
}
}
return 0;
}
Compilation message
regions.cpp: In function 'void dfs(int)':
regions.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for (int i = 0; i < adj[s].size(); i++)
| ~~^~~~~~~~~~~~~~~
regions.cpp: In function 'void dfs2(int, int)':
regions.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i = 0; i < adj[s].size(); i++)
| ~~^~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int j = 0; j < region_members[i].size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:75:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < region_members[r1].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:92:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i = 0; i < region_members[r2].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12732 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12888 KB |
Output is correct |
| 4 |
Correct |
4 ms |
12888 KB |
Output is correct |
| 5 |
Correct |
6 ms |
12888 KB |
Output is correct |
| 6 |
Correct |
11 ms |
12888 KB |
Output is correct |
| 7 |
Correct |
16 ms |
12888 KB |
Output is correct |
| 8 |
Correct |
17 ms |
12888 KB |
Output is correct |
| 9 |
Correct |
27 ms |
13400 KB |
Output is correct |
| 10 |
Correct |
49 ms |
13400 KB |
Output is correct |
| 11 |
Correct |
88 ms |
13388 KB |
Output is correct |
| 12 |
Correct |
96 ms |
14140 KB |
Output is correct |
| 13 |
Correct |
131 ms |
13576 KB |
Output is correct |
| 14 |
Correct |
207 ms |
14264 KB |
Output is correct |
| 15 |
Correct |
211 ms |
18232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
55 ms |
42948 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
57 ms |
41144 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
62 ms |
45364 KB |
Execution killed with signal 11 |
| 4 |
Correct |
181 ms |
14424 KB |
Output is correct |
| 5 |
Correct |
247 ms |
16840 KB |
Output is correct |
| 6 |
Correct |
1094 ms |
15492 KB |
Output is correct |
| 7 |
Correct |
1411 ms |
16460 KB |
Output is correct |
| 8 |
Correct |
1069 ms |
24052 KB |
Output is correct |
| 9 |
Correct |
1833 ms |
22076 KB |
Output is correct |
| 10 |
Correct |
3720 ms |
30260 KB |
Output is correct |
| 11 |
Correct |
3850 ms |
21212 KB |
Output is correct |
| 12 |
Runtime error |
147 ms |
56636 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
134 ms |
57292 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
160 ms |
82568 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
149 ms |
66372 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
149 ms |
77124 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
167 ms |
106200 KB |
Execution killed with signal 11 |
