oj.uz

Submission #1026950

# Submission time Handle Problem Language Result Execution time Memory
1026950 2024-07-18T14:51:49 Z simona1230 Regions (IOI09_regions) C++17
1 / 100
 2379 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-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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Incorrect 2 ms 10840 KB Output isn't correct
3 Incorrect 4 ms 10840 KB Output isn't correct
4 Incorrect 4 ms 10840 KB Output isn't correct
5 Incorrect 5 ms 10936 KB Output isn't correct
6 Incorrect 11 ms 11096 KB Output isn't correct
7 Incorrect 17 ms 11096 KB Output isn't correct
8 Incorrect 17 ms 11096 KB Output isn't correct
9 Incorrect 23 ms 11352 KB Output isn't correct
10 Incorrect 55 ms 11352 KB Output isn't correct
11 Incorrect 88 ms 11608 KB Output isn't correct
12 Incorrect 110 ms 12120 KB Output isn't correct
13 Incorrect 141 ms 11864 KB Output isn't correct
14 Incorrect 226 ms 12376 KB Output isn't correct
15 Incorrect 213 ms 16216 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1562 ms 16004 KB Output isn't correct
2 Incorrect 1863 ms 14160 KB Output isn't correct
3 Incorrect 2379 ms 18188 KB Output isn't correct
4 Incorrect 204 ms 12632 KB Output isn't correct
5 Incorrect 271 ms 14004 KB Output isn't correct
6 Incorrect 731 ms 36844 KB Output isn't correct
7 Incorrect 1307 ms 45892 KB Output isn't correct
8 Incorrect 1639 ms 84072 KB Output isn't correct
9 Runtime error 93 ms 39232 KB Execution killed with signal 11
10 Runtime error 1398 ms 131072 KB Execution killed with signal 9
11 Runtime error 101 ms 38224 KB Execution killed with signal 11
12 Runtime error 177 ms 44776 KB Execution killed with signal 11
13 Runtime error 163 ms 46260 KB Execution killed with signal 11
14 Runtime error 661 ms 89168 KB Execution killed with signal 11
15 Runtime error 171 ms 60752 KB Execution killed with signal 11
16 Runtime error 173 ms 78928 KB Execution killed with signal 11
17 Runtime error 612 ms 119376 KB Execution killed with signal 11