#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'
const int MXN = 200000, MXR = 25000, INF = 1e9+1;
int n, r, q;
int reg[MXN+1], tin[MXN+1], tout[MXN+1], pt = 0;
vi adj[MXN+1];
vi regList[MXR+1], regListId[MXR+1];
unordered_map<int, int> seen[MXR+1];
void dfs(int p, int parent) {
regList[reg[p]].push_back(pt);
regListId[reg[p]].push_back(p);
tin[p] = pt++;
for (int i: adj[p]) if (i != parent) dfs(i, p);
tout[p] = pt-1;
}
int main() {
#ifdef shiven
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> r >> q;
cin >> reg[0];
reg[0] -= 1;
for_(i, 1, n) {
int p; cin >> p >> reg[i];
reg[i] -= 1;
adj[p-1].push_back(i);
}
dfs(0, 0);
while (q--) {
int r1, r2; cin >> r1 >> r2;
r1 -= 1; r2 -= 1;
if (seen[r1].find(r2) != seen[r1].end()) {
cout << seen[r1][r2] << endl;
continue;
}
int ans = 0;
for (auto i: regListId[r1]) {
ans += upper_bound(regList[r2].begin(), regList[r2].end(), tout[i]) - lower_bound(regList[r2].begin(), regList[r2].end(), tin[i]+1);
}
cout << ans << endl;
seen[r1][r2] = ans;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
7552 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7552 KB |
Output is correct |
| 3 |
Correct |
8 ms |
7552 KB |
Output is correct |
| 4 |
Correct |
8 ms |
7552 KB |
Output is correct |
| 5 |
Correct |
15 ms |
7680 KB |
Output is correct |
| 6 |
Correct |
15 ms |
7788 KB |
Output is correct |
| 7 |
Correct |
45 ms |
7800 KB |
Output is correct |
| 8 |
Correct |
38 ms |
7808 KB |
Output is correct |
| 9 |
Correct |
48 ms |
8312 KB |
Output is correct |
| 10 |
Correct |
83 ms |
8452 KB |
Output is correct |
| 11 |
Correct |
132 ms |
8824 KB |
Output is correct |
| 12 |
Correct |
177 ms |
9340 KB |
Output is correct |
| 13 |
Correct |
170 ms |
9180 KB |
Output is correct |
| 14 |
Correct |
281 ms |
9736 KB |
Output is correct |
| 15 |
Correct |
219 ms |
12452 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1637 ms |
13340 KB |
Output is correct |
| 2 |
Correct |
1423 ms |
12300 KB |
Output is correct |
| 3 |
Correct |
2471 ms |
16976 KB |
Output is correct |
| 4 |
Correct |
225 ms |
10548 KB |
Output is correct |
| 5 |
Correct |
378 ms |
12412 KB |
Output is correct |
| 6 |
Correct |
543 ms |
12084 KB |
Output is correct |
| 7 |
Correct |
915 ms |
12612 KB |
Output is correct |
| 8 |
Correct |
1437 ms |
19708 KB |
Output is correct |
| 9 |
Correct |
2648 ms |
22960 KB |
Output is correct |
| 10 |
Correct |
4710 ms |
29056 KB |
Output is correct |
| 11 |
Correct |
4796 ms |
25040 KB |
Output is correct |
| 12 |
Correct |
5358 ms |
21992 KB |
Output is correct |
| 13 |
Correct |
6452 ms |
23584 KB |
Output is correct |
| 14 |
Correct |
7848 ms |
24596 KB |
Output is correct |
| 15 |
Execution timed out |
8082 ms |
30908 KB |
Time limit exceeded |
| 16 |
Correct |
7430 ms |
36568 KB |
Output is correct |
| 17 |
Correct |
6478 ms |
35028 KB |
Output is correct |
