Submission #1026950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026950		simona1230	Regions (IOI09_regions)	C++17	1 / 100	2379 ms	131072 KiB

regions

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

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

map<pair<int,int>, int> mp;

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

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

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-1;
}

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);
    }

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

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

        curr=i;
        dfs(1,0);
    }
    dfs2(1);

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

        for(int ii=0;ii<ver[r1].size();ii++)
        {
            int e1=ver[r1][ii];
            //cout<<e1<<" +";
            sum+=count_(r2,out[e1])-count_(r2,in[e1]-1);
        }
        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:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
regions.cpp: In function 'void read()':
regions.cpp:97:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int ii=0;ii<ver[r1].size();ii++)
      |                      ~~^~~~~~~~~~~~~~~

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