# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1024997 |
2024-07-16T13:55:52 Z |
MMihalev |
Regions (IOI09_regions) |
C++14 |
|
3384 ms |
41936 KB |
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
#include<array>
using namespace std;
const int MAX_N=2e5+3;
const int MAX_R=447;
vector<pair<int,int>>regions;
vector<int>nodes[MAX_N];
int calc[MAX_R+3][MAX_N];
vector<int>s[MAX_N];
int in[MAX_N];
int out[MAX_N];
int ver[MAX_N];
int T;
vector<int>g[MAX_N];
int cnt;
int n,rr,q;
int region;
int r[MAX_N];
int posregion[MAX_N];
void dfs(int u,int par)
{
if(r[u]==regions[region].second)cnt++;
else
{
calc[region][r[u]]+=cnt;
}
for(int v:g[u])
{
if(v==par)continue;
dfs(v,u);
}
if(r[u]==regions[region].second)cnt--;
}
void dfs0(int u,int par)
{
in[u]=++T;
ver[T]=u;
for(int v:g[u])
{
if(v==par)continue;
dfs0(v,u);
}
out[u]=T;
}
int query(int l,int r,int col)
{
int posl,posr,le,re;
le=0;re=s[col].size()-1;
while(le<=re)
{
int mid=(le+re)/2;
if(s[col][mid]>=l)
{
posl=mid;
re=mid-1;
}
else le=mid+1;
}
le=0;re=s[col].size()-1;
while(le<=re)
{
int mid=(le+re)/2;
if(s[col][mid]>r)
{
posr=mid;
re=mid-1;
}
else le=mid+1;
}
return (posr-posl);
}
int cntr[MAX_N];
signed main ()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>rr>>q;
cin>>r[1];
nodes[r[1]].push_back(1);
cntr[r[1]]++;
for(int i=2;i<=n;i++)
{
int x;
cin>>x>>r[i];
nodes[r[i]].push_back(i);
cntr[r[i]]++;
g[i].push_back(x);
g[x].push_back(i);
}
for(int i=1;i<=rr;i++)
{
regions.push_back({cntr[i],i});
}
sort(regions.rbegin(),regions.rend());
for(int i=0;i<rr;i++)
{
posregion[regions[i].second]=i;
if(regions[i].first>=MAX_R)
{
cnt=0;
region=i;
dfs(1,0);
}
}
dfs0(1,0);
for(int pos=1;pos<=n;pos++)
{
int u=ver[pos];
s[r[u]].push_back(pos);
}
for(int i=1;i<=rr;i++)s[i].push_back(n+1);
while(q--)
{
int r1,r2;
cin>>r1>>r2;
int ans=0;
if(regions[posregion[r1]].first>=MAX_R)
{
ans=calc[posregion[r1]][r2];
}
else
{
for(int u:nodes[r1])
{
ans+=query(in[u],out[u],r2);
}
}
cout<<ans<<"\n";
cout.flush();
}
return 0;
}
Compilation message
regions.cpp: In function 'int query(int, int, int)':
regions.cpp:86:22: warning: 'posl' may be used uninitialized in this function [-Wmaybe-uninitialized]
86 | return (posr-posl);
| ^
regions.cpp:86:22: warning: 'posr' may be used uninitialized in this function [-Wmaybe-uninitialized]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
16984 KB |
Output is correct |
2 |
Correct |
3 ms |
16984 KB |
Output is correct |
3 |
Correct |
4 ms |
16812 KB |
Output is correct |
4 |
Correct |
5 ms |
16984 KB |
Output is correct |
5 |
Correct |
8 ms |
16984 KB |
Output is correct |
6 |
Correct |
10 ms |
16992 KB |
Output is correct |
7 |
Correct |
15 ms |
16984 KB |
Output is correct |
8 |
Correct |
19 ms |
16984 KB |
Output is correct |
9 |
Correct |
25 ms |
17496 KB |
Output is correct |
10 |
Correct |
48 ms |
17496 KB |
Output is correct |
11 |
Correct |
79 ms |
17752 KB |
Output is correct |
12 |
Correct |
95 ms |
18264 KB |
Output is correct |
13 |
Correct |
138 ms |
18264 KB |
Output is correct |
14 |
Correct |
204 ms |
18776 KB |
Output is correct |
15 |
Correct |
210 ms |
21332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1510 ms |
22136 KB |
Output is correct |
2 |
Correct |
1783 ms |
21680 KB |
Output is correct |
3 |
Correct |
2406 ms |
23896 KB |
Output is correct |
4 |
Correct |
213 ms |
19032 KB |
Output is correct |
5 |
Correct |
259 ms |
20312 KB |
Output is correct |
6 |
Correct |
454 ms |
22488 KB |
Output is correct |
7 |
Correct |
1256 ms |
22252 KB |
Output is correct |
8 |
Correct |
826 ms |
31568 KB |
Output is correct |
9 |
Correct |
1867 ms |
26960 KB |
Output is correct |
10 |
Correct |
2858 ms |
38860 KB |
Output is correct |
11 |
Correct |
3384 ms |
30688 KB |
Output is correct |
12 |
Correct |
1118 ms |
29372 KB |
Output is correct |
13 |
Correct |
1473 ms |
30384 KB |
Output is correct |
14 |
Correct |
1878 ms |
32100 KB |
Output is correct |
15 |
Correct |
2589 ms |
34684 KB |
Output is correct |
16 |
Correct |
2552 ms |
41780 KB |
Output is correct |
17 |
Correct |
2297 ms |
41936 KB |
Output is correct |