oj.uz

Submission #1026952

# Submission time Handle Problem Language Result Execution time Memory
1026952 2024-07-18T14:58:03 Z simona1230 Regions (IOI09_regions) C++17
95 / 100
 3532 ms 131072 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;

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[200001],ver[200001];
int num;
int in[200001],out[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);
    }

    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 3 ms 16728 KB Output is correct
2 Correct 2 ms 16816 KB Output is correct
3 Correct 3 ms 16728 KB Output is correct
4 Correct 5 ms 16728 KB Output is correct
5 Correct 6 ms 16728 KB Output is correct
6 Correct 11 ms 16728 KB Output is correct
7 Correct 20 ms 16728 KB Output is correct
8 Correct 17 ms 16724 KB Output is correct
9 Correct 28 ms 17240 KB Output is correct
10 Correct 50 ms 17196 KB Output is correct
11 Correct 87 ms 17496 KB Output is correct
12 Correct 95 ms 18008 KB Output is correct
13 Correct 132 ms 17496 KB Output is correct
14 Correct 221 ms 18264 KB Output is correct
15 Correct 228 ms 21848 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1514 ms 21520 KB Output is correct
2 Correct 1859 ms 19556 KB Output is correct
3 Correct 2377 ms 23648 KB Output is correct
4 Correct 201 ms 18264 KB Output is correct
5 Correct 284 ms 19800 KB Output is correct
6 Correct 749 ms 42576 KB Output is correct
7 Correct 1311 ms 51412 KB Output is correct
8 Correct 1767 ms 89380 KB Output is correct
9 Correct 1953 ms 24516 KB Output is correct
10 Runtime error 1399 ms 131072 KB Execution killed with signal 9
11 Correct 3532 ms 23796 KB Output is correct
12 Correct 1158 ms 27224 KB Output is correct
13 Correct 1607 ms 27984 KB Output is correct
14 Correct 2248 ms 49128 KB Output is correct
15 Correct 2395 ms 35084 KB Output is correct
16 Correct 2186 ms 43948 KB Output is correct
17 Correct 2529 ms 64000 KB Output is correct