oj.uz

Submission #1026951

# Submission time Handle Problem Language Result Execution time Memory
1026951 2024-07-18T14:55:59 Z simona1230 Regions (IOI09_regions) C++17
55 / 100
 2356 ms 131072 KB 
#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;
}

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 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: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:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int j=0;j<ver[r1].size();j++)
      |                     ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 3 ms 10920 KB Output is correct
4 Correct 4 ms 10840 KB Output is correct
5 Correct 6 ms 10840 KB Output is correct
6 Correct 11 ms 11096 KB Output is correct
7 Correct 16 ms 11096 KB Output is correct
8 Correct 16 ms 11096 KB Output is correct
9 Correct 27 ms 11352 KB Output is correct
10 Correct 55 ms 11352 KB Output is correct
11 Correct 81 ms 11608 KB Output is correct
12 Correct 106 ms 12120 KB Output is correct
13 Correct 140 ms 11864 KB Output is correct
14 Correct 227 ms 12368 KB Output is correct
15 Correct 227 ms 16176 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1564 ms 15996 KB Output is correct
2 Correct 1871 ms 14044 KB Output is correct
3 Correct 2356 ms 18180 KB Output is correct
4 Correct 209 ms 12632 KB Output is correct
5 Correct 275 ms 14168 KB Output is correct
6 Correct 777 ms 37080 KB Output is correct
7 Correct 1343 ms 45980 KB Output is correct
8 Correct 1759 ms 84020 KB Output is correct
9 Runtime error 83 ms 39248 KB Execution killed with signal 11
10 Runtime error 1476 ms 131072 KB Execution killed with signal 9
11 Runtime error 134 ms 38224 KB Execution killed with signal 11
12 Runtime error 143 ms 44692 KB Execution killed with signal 11
13 Runtime error 148 ms 46124 KB Execution killed with signal 11
14 Runtime error 645 ms 89240 KB Execution killed with signal 11
15 Runtime error 161 ms 60616 KB Execution killed with signal 11
16 Runtime error 174 ms 79008 KB Execution killed with signal 11
17 Runtime error 610 ms 119372 KB Execution killed with signal 11