#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f1 fisrt
#define s2 second
using ii = pair<int, int>;
using ll = long long;
const int MAXN = 2e5 + 69;
const int MAXR = 25069;
const int inf = 1e9 + 69;
int N, R, Q;
int region[MAXN], pos[MAXN], sz[MAXN];
vector<int> adj[MAXN];
vector<ii> item[MAXR];
int depth[MAXR];
static int cur_pos = 0;
inline int dfs_sz(int node)
{
pos[node] = cur_pos++;
sz[pos[node]] = 1;
depth[region[node]]++;
item[region[node]].pb({pos[node], depth[region[node]]});
for (int to : adj[node])
sz[pos[node]] += dfs_sz(to);
depth[region[node]]--;
return sz[pos[node]];
}
inline ll query1(const int &r1, const int &r2)
{
ll res = 0;
for (auto [node, dep] : item[r1])
{
int l = (int)(lower_bound(item[r2].begin(), item[r2].end(), mp(pos[node], inf)) - item[r2].begin());
int r = (int)(lower_bound(item[r2].begin(), item[r2].end(), mp(pos[node] + sz[node] - 1, inf)) - item[r2].begin());
res += (r-l);
}
return res;
}
inline ll query2(const int &r1, const int &r2)
{
ll res = 0;
for (auto [node, dep] : item[r2])
{
auto it = lower_bound(item[r1].begin(), item[r1].end(), mp(pos[node], inf));
if (it == item[r1].begin())
continue;
res += prev(it) -> s2;
}
return res;
}
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> R >> Q;
for (int i = 1, p; i <= N; ++i)
{
if (i > 1)
{
cin >> p;
adj[p].pb(i);
}
cin >> region[i];
}
dfs_sz(1);
map<ii, ll> memo;
for (int r1, r2; Q--;)
{
cin >> r1 >> r2;
if (!memo.count({r1, r2}))
{
if (item[r1].size() < item[r2].size())
memo[{r1, r2}] = query1(r1, r2);
else memo[{r1, r2}] = query2(r1, r2);
}
cout << memo[{r1, r2}] << endl;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
5584 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
5584 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
5584 KB |
Output isn't correct |
| 4 |
Incorrect |
9 ms |
5648 KB |
Output isn't correct |
| 5 |
Incorrect |
13 ms |
5584 KB |
Output isn't correct |
| 6 |
Incorrect |
26 ms |
5840 KB |
Output isn't correct |
| 7 |
Incorrect |
37 ms |
5780 KB |
Output isn't correct |
| 8 |
Incorrect |
33 ms |
5876 KB |
Output isn't correct |
| 9 |
Incorrect |
26 ms |
6328 KB |
Output isn't correct |
| 10 |
Incorrect |
98 ms |
6504 KB |
Output isn't correct |
| 11 |
Incorrect |
124 ms |
6992 KB |
Output isn't correct |
| 12 |
Incorrect |
123 ms |
7532 KB |
Output isn't correct |
| 13 |
Incorrect |
226 ms |
7300 KB |
Output isn't correct |
| 14 |
Incorrect |
268 ms |
8184 KB |
Output isn't correct |
| 15 |
Incorrect |
302 ms |
10076 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1200 ms |
11824 KB |
Output isn't correct |
| 2 |
Incorrect |
1424 ms |
10708 KB |
Output isn't correct |
| 3 |
Incorrect |
1853 ms |
15528 KB |
Output isn't correct |
| 4 |
Incorrect |
302 ms |
8716 KB |
Output isn't correct |
| 5 |
Incorrect |
409 ms |
10552 KB |
Output isn't correct |
| 6 |
Incorrect |
606 ms |
10392 KB |
Output isn't correct |
| 7 |
Incorrect |
916 ms |
10568 KB |
Output isn't correct |
| 8 |
Incorrect |
1157 ms |
17336 KB |
Output isn't correct |
| 9 |
Incorrect |
2080 ms |
22764 KB |
Output isn't correct |
| 10 |
Incorrect |
3713 ms |
28144 KB |
Output isn't correct |
| 11 |
Incorrect |
4360 ms |
26064 KB |
Output isn't correct |
| 12 |
Incorrect |
1114 ms |
21108 KB |
Output isn't correct |
| 13 |
Incorrect |
1839 ms |
23120 KB |
Output isn't correct |
| 14 |
Incorrect |
2136 ms |
24320 KB |
Output isn't correct |
| 15 |
Incorrect |
3589 ms |
30300 KB |
Output isn't correct |
| 16 |
Incorrect |
3155 ms |
34608 KB |
Output isn't correct |
| 17 |
Incorrect |
3484 ms |
33580 KB |
Output isn't correct |
