#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, M = 25e3 + 5, mod = 1e9 + 7, B = 2000; // !
int t, a[N], id[M], cur, cnt[M], CN2[105][M], CN1[M][105], dp[M][105], timer;
vector<pair<int,int>> reg[M];
vector<int> V[N];
void dfs(int u) {
++timer;
reg[a[u]].push_back({timer, 1});
++cnt[id[a[u]]];
for(int j = 1; j <= cur; j++) {
CN2[j][u] += cnt[j];
}
for(int i = 0; i < V[u].size(); i++) {
int v = V[u][i];
dfs(v);
for(int j = 1; j <= cur; j++) {
dp[u][j] += dp[v][j];
}
}
--cnt[id[a[u]]];
++dp[u][id[a[u]]];
for(int j = 1; j <= cur; j++) {
CN1[u][j] += dp[u][j];
}
reg[a[u]].push_back({timer + 1, 0});
}
main(){
int n, r, q;
cin >> n >> r >> q;
for(int i = 1; i <= n; i++) {
if(i >= 2) {
int k; cin >> k;
V[k].push_back(i);
}
cin >> a[i];
++cnt[a[i]];
}
// cout << "+" << endl;
cur = 0;
for(int i = 1; i <= r; i++) {
if(cnt[i] >= B) {
id[i] = ++cur;
// val[cur] = i;
}
cnt[i] = 0;
}
dfs(1);
while(q--) {
int u, v;
cin >> u >> v;
if(id[u]) {
cout << CN2[id[u]][v] << endl;
} else if(id[v]) {
cout << CN2[u][id[v]] << endl;
} else {
int l = -1;
int cn = 0, ans = 0;
for(int i = 0; i < reg[u].size(); i++) {
while(l + 1 < (int)reg[v].size() && reg[v][l + 1].f < reg[u][i].f) {
++l;
cn += reg[v][l].s;
}
ans += cn * (reg[u][i].s ? -1 : 1);
}
cout << ans << endl;
}
}
}
Compilation message
regions.cpp: In function 'void dfs(long long int)':
regions.cpp:18:22: 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]
18 | for(int i = 0; i < V[u].size(); i++) {
| ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
32 | main(){
| ^~~~
regions.cpp: In function 'int main()':
regions.cpp:63:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i = 0; i < reg[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5584 KB |
Output is correct |
2 |
Correct |
3 ms |
5584 KB |
Output is correct |
3 |
Correct |
5 ms |
5584 KB |
Output is correct |
4 |
Correct |
6 ms |
5712 KB |
Output is correct |
5 |
Correct |
6 ms |
5968 KB |
Output is correct |
6 |
Correct |
15 ms |
6352 KB |
Output is correct |
7 |
Correct |
34 ms |
6872 KB |
Output is correct |
8 |
Correct |
43 ms |
7424 KB |
Output is correct |
9 |
Correct |
48 ms |
10832 KB |
Output is correct |
10 |
Correct |
93 ms |
14672 KB |
Output is correct |
11 |
Correct |
95 ms |
19280 KB |
Output is correct |
12 |
Correct |
119 ms |
24368 KB |
Output is correct |
13 |
Correct |
118 ms |
27336 KB |
Output is correct |
14 |
Correct |
155 ms |
33172 KB |
Output is correct |
15 |
Correct |
174 ms |
47828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
106 ms |
113172 KB |
Execution killed with signal 11 |
2 |
Runtime error |
109 ms |
95852 KB |
Execution killed with signal 11 |
3 |
Runtime error |
52 ms |
28716 KB |
Execution killed with signal 11 |
4 |
Correct |
273 ms |
33140 KB |
Output is correct |
5 |
Correct |
268 ms |
42696 KB |
Output is correct |
6 |
Correct |
689 ms |
52892 KB |
Output is correct |
7 |
Correct |
1063 ms |
69440 KB |
Output is correct |
8 |
Runtime error |
106 ms |
103116 KB |
Execution killed with signal 11 |
9 |
Runtime error |
130 ms |
50024 KB |
Execution killed with signal 11 |
10 |
Runtime error |
136 ms |
52928 KB |
Execution killed with signal 11 |
11 |
Runtime error |
151 ms |
95100 KB |
Execution killed with signal 11 |
12 |
Runtime error |
209 ms |
131072 KB |
Execution killed with signal 11 |
13 |
Runtime error |
161 ms |
107048 KB |
Execution killed with signal 11 |
14 |
Runtime error |
217 ms |
131072 KB |
Execution killed with signal 11 |
15 |
Runtime error |
117 ms |
45372 KB |
Execution killed with signal 11 |
16 |
Runtime error |
166 ms |
92812 KB |
Execution killed with signal 11 |
17 |
Runtime error |
142 ms |
78080 KB |
Execution killed with signal 11 |