#include <bits/stdc++.h>
using namespace std;
vector<int> child[200005], vec[25005], ans[25005][2], tmp;
vector<pair<int, pair<int, bool> > > tt;
int a[200005][2], region[200005];
vector<pair<int, bool> > t;
void dfs(int u)
{
a[u][0]=t.size();
t.push_back({u, 0});
for (int v:child[u])
dfs(v);
a[u][1]=t.size();
t.push_back({u, 1});
}
int main()
{
int n, m, q;
cin >> n >> m >> q;
for (int i=1; i<=n; i++)
{
if (i>1)
{
int x;
cin >> x;
child[x].push_back(i);
}
cin >> region[i];
vec[region[i]].push_back(i);
}
dfs(1);
for (int i=1; i<=m; i++)
{
if (vec[i].size()*vec[i].size()>n)
{
for (int j=0; j<=m; j++)
{
ans[i][0].push_back(0);
ans[i][1].push_back(0);
}
int cur=0;
for (int j=0; j<t.size(); j++)
{
if (region[t[j].first]==i)
cur+=1-t[j].second*2;
else
ans[i][0][region[t[j].first]]+=cur*t[j].second;
}
tmp.clear();
for (int j=0; j<t.size(); j++)
{
if (region[t[j].first]==i)
cur+=t[j].second;
else if (t[j].second)
{
ans[i][1][region[tmp[tmp.size()-1]]]+=cur;
cur+=tmp[tmp.size()-2];
tmp.pop_back();
tmp.pop_back();
}
else
{
tmp.push_back(cur);
tmp.push_back(t[j].first);
cur=0;
}
}
}
}
for (int i=1; i<=q; i++)
{
int x, y;
cin >> x >> y;
if (vec[x].size()*vec[x].size()>n)
cout << ans[x][0][y] << '\n';
else if (vec[y].size()*vec[y].size()>n)
cout << ans[y][1][x] << '\n';
else
{
tt.clear();
for (int u:vec[x])
{
tt.push_back({a[u][0], {u, 0}});
tt.push_back({a[u][1], {u, 1}});
}
for (int u:vec[y])
{
tt.push_back({a[u][0], {u, 0}});
tt.push_back({a[u][1], {u, 1}});
}
// sort(tt.begin(), tt.end());
int cur=0, res=0;
for (int j=0; j<tt.size(); j++)
{
if (region[tt[j].second.first]==x)
cur+=1-tt[j].second.second*2;
else
res+=cur*tt[j].second.second;
}
cout << res << '\n';
}
fflush(stdout);
}
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:34:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
34 | if (vec[i].size()*vec[i].size()>n)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:42:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int j=0; j<t.size(); j++)
| ~^~~~~~~~~
regions.cpp:50:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int j=0; j<t.size(); j++)
| ~^~~~~~~~~
regions.cpp:74:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
74 | if (vec[x].size()*vec[x].size()>n)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:76:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
76 | else if (vec[y].size()*vec[y].size()>n)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:93:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, bool> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int j=0; j<tt.size(); j++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6736 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6736 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
6736 KB |
Output isn't correct |
| 4 |
Incorrect |
8 ms |
6736 KB |
Output isn't correct |
| 5 |
Incorrect |
9 ms |
6736 KB |
Output isn't correct |
| 6 |
Incorrect |
13 ms |
6880 KB |
Output isn't correct |
| 7 |
Incorrect |
28 ms |
6844 KB |
Output isn't correct |
| 8 |
Incorrect |
32 ms |
6864 KB |
Output isn't correct |
| 9 |
Incorrect |
55 ms |
7504 KB |
Output isn't correct |
| 10 |
Incorrect |
79 ms |
7632 KB |
Output isn't correct |
| 11 |
Incorrect |
126 ms |
7888 KB |
Output isn't correct |
| 12 |
Incorrect |
142 ms |
8572 KB |
Output isn't correct |
| 13 |
Incorrect |
100 ms |
8200 KB |
Output isn't correct |
| 14 |
Incorrect |
240 ms |
8784 KB |
Output isn't correct |
| 15 |
Incorrect |
323 ms |
12612 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1010 ms |
13376 KB |
Output isn't correct |
| 2 |
Incorrect |
1101 ms |
11864 KB |
Output isn't correct |
| 3 |
Incorrect |
1862 ms |
15448 KB |
Output isn't correct |
| 4 |
Incorrect |
308 ms |
8828 KB |
Output isn't correct |
| 5 |
Incorrect |
410 ms |
11344 KB |
Output isn't correct |
| 6 |
Incorrect |
626 ms |
13968 KB |
Output isn't correct |
| 7 |
Incorrect |
937 ms |
15816 KB |
Output isn't correct |
| 8 |
Incorrect |
1140 ms |
27104 KB |
Output isn't correct |
| 9 |
Incorrect |
2228 ms |
19428 KB |
Output isn't correct |
| 10 |
Incorrect |
2396 ms |
45232 KB |
Output isn't correct |
| 11 |
Incorrect |
3055 ms |
18616 KB |
Output isn't correct |
| 12 |
Incorrect |
788 ms |
20460 KB |
Output isn't correct |
| 13 |
Incorrect |
1511 ms |
20880 KB |
Output isn't correct |
| 14 |
Incorrect |
1813 ms |
23284 KB |
Output isn't correct |
| 15 |
Incorrect |
2367 ms |
25552 KB |
Output isn't correct |
| 16 |
Incorrect |
2671 ms |
35464 KB |
Output isn't correct |
| 17 |
Incorrect |
2348 ms |
36324 KB |
Output isn't correct |
