Submission #1026957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026957		simona1230	Regions (IOI09_regions)	C++17	100 / 100	3614 ms	41808 KiB

regions

#include<bits/stdc++.h>
using namespace std;

int n,r,q;
int c[200001];
int h[200001];
vector<int> v[200001];
int curr,s,val;

int ans[500][25001];

void dfs(int i,int cnt)
{
    if(h[i]==val)cnt++;
    //cout<<i<<" - "<<curr<<" "<<c[i]<<" "<<cnt<<endl;
    ans[curr][h[i]]+=cnt;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        dfs(nb,cnt);
    }
}

vector<int> pos[200001],ver[200001];
int num;
int in[200001],out[200001];
int other[200001];

void dfs2(int i)
{
    in[i]=++num;
    pos[h[i]].push_back(in[i]);
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        dfs2(nb);
    }
    out[i]=num;
}

int count_(int r2,int idx)
{
    if(pos[r2].size()==0||pos[r2][0]>idx)return 0;
    int l=0,r=pos[r2].size()-1;
    int cnt=0;
    while(l<=r)
    {
        int m=(l+r)/2;
        if(pos[r2][m]<=idx)
        {
            cnt=m+1;
            l=m+1;
        }
        else r=m-1;
    }
    return cnt;
}

void read()
{
    cin>>n>>r>>q;
    s=sqrt(n);

    cin>>h[1];
    c[h[1]]++;
    ver[h[1]].push_back(1);
    for(int i=2;i<=n;i++)
    {
        int x;
        cin>>x>>h[i];
        c[h[i]]++;
        v[x].push_back(i);
        ver[h[i]].push_back(i);
    }

    int hey=0;

    for(int i=1;i<=r;i++)
    {
        if(c[i]<s)continue;

        //cout<<i<<"!"<<endl;

        curr=hey;
        val=i;
        dfs(1,0);
        other[i]=hey++;
    }
    dfs2(1);

    for(int i=1;i<=q;i++)
    {
        int r1,r2;
        cin>>r1>>r2;
        if(c[r1]>=s)
        {
            cout<<ans[other[r1]][r2]<<endl;
            continue;
        }
        int sum=0;

        for(int j=0;j<ver[r1].size();j++)
        {
            int e1=ver[r1][j];
            //cout<<e1<<" - "<<in[e1]<<" "<<out[e1]<<endl;
            sum+=count_(r2,out[e1])-count_(r2,in[e1]-1);
        }

        /*for(int j=0;j<pos[r2].size();j++)
            cout<<pos[r2][j]<<" ";
        cout<<endl;
        cout<<endl;*/
        cout<<sum<<endl;
    }
}



int main()
{
    read();
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
regions.cpp: In function 'void dfs2(int)':
regions.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
regions.cpp: In function 'void read()':
regions.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int j=0;j<ver[r1].size();j++)
      |                     ~^~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85