oj.uz

Submission #1026957

# Submission time Handle Problem Language Result Execution time Memory
1026957 2024-07-18T15:09:32 Z simona1230 Regions (IOI09_regions) C++17
100 / 100
 3614 ms 41808 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18776 KB Output is correct
4 Correct 6 ms 18884 KB Output is correct
5 Correct 6 ms 18776 KB Output is correct
6 Correct 12 ms 18776 KB Output is correct
7 Correct 17 ms 18776 KB Output is correct
8 Correct 25 ms 18776 KB Output is correct
9 Correct 42 ms 19288 KB Output is correct
10 Correct 56 ms 19288 KB Output is correct
11 Correct 95 ms 19548 KB Output is correct
12 Correct 98 ms 19800 KB Output is correct
13 Correct 146 ms 19544 KB Output is correct
14 Correct 219 ms 20056 KB Output is correct
15 Correct 210 ms 22360 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1468 ms 24708 KB Output is correct
2 Correct 1813 ms 23288 KB Output is correct
3 Correct 2318 ms 26324 KB Output is correct
4 Correct 219 ms 20056 KB Output is correct
5 Correct 295 ms 21592 KB Output is correct
6 Correct 454 ms 27216 KB Output is correct
7 Correct 965 ms 26192 KB Output is correct
8 Correct 848 ms 36944 KB Output is correct
9 Correct 1976 ms 26680 KB Output is correct
10 Correct 2463 ms 41808 KB Output is correct
11 Correct 3614 ms 26040 KB Output is correct
12 Correct 1181 ms 27472 KB Output is correct
13 Correct 1663 ms 27728 KB Output is correct
14 Correct 1886 ms 29768 KB Output is correct
15 Correct 2674 ms 32072 KB Output is correct
16 Correct 2564 ms 37352 KB Output is correct
17 Correct 2400 ms 38232 KB Output is correct