| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 964920 |
2024-04-17T17:44:29 Z |
PieArmy |
Regions (IOI09_regions) |
C++17 |
|
2150 ms |
79760 KB |
typedef long long ll;
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n,sq,R,Q;
int renk[200001],fazlapos[25001],bas[200001],son[200001];
int pre[25001][447],pre2[447][25001];
vector<int>child[200001],var[25001],sirali[25001];
int cal(int a,int b){
if(sirali[b].size()==0||sirali[a].size()==0){
return 0;
}
if(sirali[b].size()>sq){
return pre[a][fazlapos[b]];
}
if(sirali[a].size()>sq){
return pre2[fazlapos[a]][b];
}
int sta[sirali[a].size()];
int tavan=-1;
int apos=0;
int ans=0;
for(int i=0;i<sirali[b].size();i++){
while(tavan!=-1&&son[sta[tavan]]<bas[var[b][i]]){
tavan--;
}
while(apos<sirali[a].size()&&bas[sirali[a][apos]]<=bas[var[b][i]]){
if(son[sirali[a][apos]]>=bas[var[b][i]]){
tavan++;
sta[tavan]=sirali[a][apos];
}
apos++;
}
ans+=tavan+1;
}
return ans;
}
int main(){
cin>>n>>R>>Q;
sq=sqrt(n);
cin>>renk[1];
int time=0;
sirali[renk[1]].pb(1);
for(int &x:fazlapos)
x=-1;
for(int i=2;i<=n;i++){
int par;cin>>par;
child[par].pb(i);
cin>>renk[i];
if(sirali[renk[i]].size()==sq){
fazlapos[renk[i]]=time;
time++;
}
sirali[renk[i]].pb(i);
}
function<ll(int,int)>f=[&](int pos,int tur)->ll{
ll res=0;
for(int x:child[pos]){
res+=f(x,tur);
}
if(renk[pos]==tur)return res+1;
pre[renk[pos]][fazlapos[tur]]+=res;
return res;
};
function<void(int,int,ll)>f2=[&](int pos,int tur,ll sum)->void{
if(renk[pos]!=tur)pre2[fazlapos[tur]][renk[pos]]+=sum;
else sum++;
for(int x:child[pos]){
f2(x,tur,sum);
}
};
for(int i=1;i<=R;i++){
if(fazlapos[i]==-1)continue;
f(1,i);
f2(1,i,0);
}
time=1;
function<void(int)>turla=[&](int pos)->void{
if(sirali[renk[pos]].size()<=sq){
bas[pos]=time;
var[renk[pos]].pb(pos);
}
time++;
for(int x:child[pos]){
turla(x);
}
child[pos].clear();
son[pos]=time-1;
};
turla(1);
for(int i=1;i<=R;i++){
if(sirali[i].size()>sq)continue;
sort(sirali[i].begin(),sirali[i].end(),[&](const int &x,const int &y){
if(bas[x]==bas[y]){
return son[x]<son[y];
}
return bas[x]<bas[y];
});
}
while(Q--){
int a,b;cin>>a>>b;
cout<<cal(a,b)<<endl;
}
}
Compilation message
regions.cpp: In function 'int cal(int, int)':
regions.cpp:15:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
15 | if(sirali[b].size()>sq){
| ~~~~~~~~~~~~~~~~^~~
regions.cpp:18:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
18 | if(sirali[a].size()>sq){
| ~~~~~~~~~~~~~~~~^~~
regions.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i=0;i<sirali[b].size();i++){
| ~^~~~~~~~~~~~~~~~~
regions.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | while(apos<sirali[a].size()&&bas[sirali[a][apos]]<=bas[var[b][i]]){
| ~~~~^~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:53:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
53 | if(sirali[renk[i]].size()==sq){
| ~~~~~~~~~~~~~~~~~~~~~~^~~~
regions.cpp: In lambda function:
regions.cpp:82:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
82 | if(sirali[renk[pos]].size()<=sq){
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'int main()':
regions.cpp:95:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
95 | if(sirali[i].size()>sq)continue;
| ~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8792 KB |
Output is correct |
| 4 |
Correct |
4 ms |
8792 KB |
Output is correct |
| 5 |
Correct |
6 ms |
8788 KB |
Output is correct |
| 6 |
Correct |
11 ms |
8792 KB |
Output is correct |
| 7 |
Correct |
19 ms |
8792 KB |
Output is correct |
| 8 |
Correct |
20 ms |
8792 KB |
Output is correct |
| 9 |
Correct |
34 ms |
9344 KB |
Output is correct |
| 10 |
Correct |
48 ms |
9304 KB |
Output is correct |
| 11 |
Correct |
72 ms |
9560 KB |
Output is correct |
| 12 |
Correct |
85 ms |
10136 KB |
Output is correct |
| 13 |
Correct |
110 ms |
9504 KB |
Output is correct |
| 14 |
Correct |
139 ms |
12316 KB |
Output is correct |
| 15 |
Correct |
173 ms |
16692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
698 ms |
17368 KB |
Output is correct |
| 2 |
Correct |
764 ms |
15628 KB |
Output is correct |
| 3 |
Correct |
1244 ms |
20132 KB |
Output is correct |
| 4 |
Correct |
174 ms |
10324 KB |
Output is correct |
| 5 |
Correct |
257 ms |
12320 KB |
Output is correct |
| 6 |
Correct |
544 ms |
31936 KB |
Output is correct |
| 7 |
Correct |
796 ms |
36832 KB |
Output is correct |
| 8 |
Correct |
1056 ms |
48776 KB |
Output is correct |
| 9 |
Correct |
1320 ms |
17384 KB |
Output is correct |
| 10 |
Correct |
2150 ms |
79308 KB |
Output is correct |
| 11 |
Correct |
2113 ms |
17028 KB |
Output is correct |
| 12 |
Correct |
882 ms |
47024 KB |
Output is correct |
| 13 |
Correct |
1125 ms |
47884 KB |
Output is correct |
| 14 |
Correct |
1631 ms |
57396 KB |
Output is correct |
| 15 |
Correct |
1817 ms |
68872 KB |
Output is correct |
| 16 |
Correct |
1861 ms |
79760 KB |
Output is correct |
| 17 |
Correct |
1930 ms |
73256 KB |
Output is correct |
