#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 u:vec[i])
// tmp.push_back(a[u][0]);
// sort(tmp.begin(), tmp.end());
// for (int j=1; j<=n; j++)
// {
// int x=lower_bound(tmp.begin(), tmp.end(), a[j][0])-tmp.begin();
// int y=lower_bound(tmp.begin(), tmp.end(), a[j][1])-tmp.begin();
// ans[i][1][region[j]]+=y-x;
// }
}
}
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:83:40: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
83 | if (vec[x].size()*vec[x].size()>n)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:85:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
85 | else if (vec[y].size()*vec[y].size()>n)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
regions.cpp:102: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]
102 | for (int j=0; j<tt.size(); j++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6736 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6736 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6736 KB |
Output is correct |
| 4 |
Correct |
5 ms |
6736 KB |
Output is correct |
| 5 |
Correct |
12 ms |
6736 KB |
Output is correct |
| 6 |
Correct |
25 ms |
6864 KB |
Output is correct |
| 7 |
Correct |
38 ms |
6864 KB |
Output is correct |
| 8 |
Correct |
39 ms |
6864 KB |
Output is correct |
| 9 |
Correct |
61 ms |
7520 KB |
Output is correct |
| 10 |
Correct |
111 ms |
7632 KB |
Output is correct |
| 11 |
Correct |
195 ms |
7888 KB |
Output is correct |
| 12 |
Correct |
228 ms |
8660 KB |
Output is correct |
| 13 |
Correct |
325 ms |
8200 KB |
Output is correct |
| 14 |
Correct |
514 ms |
8784 KB |
Output is correct |
| 15 |
Correct |
613 ms |
12672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2035 ms |
13340 KB |
Output is correct |
| 2 |
Correct |
2333 ms |
11964 KB |
Output is correct |
| 3 |
Correct |
4566 ms |
15336 KB |
Output is correct |
| 4 |
Correct |
400 ms |
8760 KB |
Output is correct |
| 5 |
Correct |
573 ms |
11336 KB |
Output is correct |
| 6 |
Correct |
617 ms |
14012 KB |
Output is correct |
| 7 |
Correct |
1136 ms |
15836 KB |
Output is correct |
| 8 |
Correct |
1390 ms |
27204 KB |
Output is correct |
| 9 |
Correct |
4880 ms |
19372 KB |
Output is correct |
| 10 |
Correct |
3338 ms |
45244 KB |
Output is correct |
| 11 |
Execution timed out |
8054 ms |
18732 KB |
Time limit exceeded |
| 12 |
Correct |
1997 ms |
20372 KB |
Output is correct |
| 13 |
Correct |
3142 ms |
20856 KB |
Output is correct |
| 14 |
Correct |
3181 ms |
23256 KB |
Output is correct |
| 15 |
Correct |
6031 ms |
25612 KB |
Output is correct |
| 16 |
Correct |
5562 ms |
35448 KB |
Output is correct |
| 17 |
Correct |
4762 ms |
36340 KB |
Output is correct |
