oj.uz

Submission #1024997

# Submission time Handle Problem Language Result Execution time Memory
1024997 2024-07-16T13:55:52 Z MMihalev Regions (IOI09_regions) C++14
100 / 100
 3384 ms 41936 KB 
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
#include<array>
using namespace std;
const int MAX_N=2e5+3;
const int MAX_R=447;
vector<pair<int,int>>regions;
vector<int>nodes[MAX_N];
int calc[MAX_R+3][MAX_N];
vector<int>s[MAX_N];
int in[MAX_N];
int out[MAX_N];
int ver[MAX_N];
int T;
vector<int>g[MAX_N];
int cnt;
int n,rr,q;
int region;
int r[MAX_N];
int posregion[MAX_N];
void dfs(int u,int par)
{
    if(r[u]==regions[region].second)cnt++;
    else
    {
        calc[region][r[u]]+=cnt;
    }

    for(int v:g[u])
    {
        if(v==par)continue;
        dfs(v,u);
    }

    if(r[u]==regions[region].second)cnt--;
}
void dfs0(int u,int par)
{
    in[u]=++T;
    ver[T]=u;
    for(int v:g[u])
    {
        if(v==par)continue;
        dfs0(v,u);
    }
    out[u]=T;
}
int query(int l,int r,int col)
{
    int posl,posr,le,re;
    le=0;re=s[col].size()-1;
    while(le<=re)
    {
        int mid=(le+re)/2;
        if(s[col][mid]>=l)
        {
            posl=mid;
            re=mid-1;
        }
        else le=mid+1;
    }

    le=0;re=s[col].size()-1;
    while(le<=re)
    {
        int mid=(le+re)/2;
        if(s[col][mid]>r)
        {
            posr=mid;
            re=mid-1;
        }
        else le=mid+1;
    }

    return (posr-posl);
}
int cntr[MAX_N];
signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>rr>>q;
    cin>>r[1];
    nodes[r[1]].push_back(1);
    cntr[r[1]]++;
    for(int i=2;i<=n;i++)
    {
        int x;
        cin>>x>>r[i];
        nodes[r[i]].push_back(i);
        cntr[r[i]]++;
        g[i].push_back(x);
        g[x].push_back(i);
    }

    for(int i=1;i<=rr;i++)
    {
        regions.push_back({cntr[i],i});
    }
    sort(regions.rbegin(),regions.rend());

    for(int i=0;i<rr;i++)
    {
        posregion[regions[i].second]=i;
        if(regions[i].first>=MAX_R)
        {
            cnt=0;
            region=i;
            dfs(1,0);
        }
    }

    dfs0(1,0);

    for(int pos=1;pos<=n;pos++)
    {
        int u=ver[pos];
        s[r[u]].push_back(pos);
    }

    for(int i=1;i<=rr;i++)s[i].push_back(n+1);

    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        int ans=0;
        if(regions[posregion[r1]].first>=MAX_R)
        {
            ans=calc[posregion[r1]][r2];
        }
        else
        {
            for(int u:nodes[r1])
            {
                ans+=query(in[u],out[u],r2);
            }
        }
        cout<<ans<<"\n";
        cout.flush();
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int query(int, int, int)':
regions.cpp:86:22: warning: 'posl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     return (posr-posl);
      |                      ^
regions.cpp:86:22: warning: 'posr' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 4 ms 16812 KB Output is correct
4 Correct 5 ms 16984 KB Output is correct
5 Correct 8 ms 16984 KB Output is correct
6 Correct 10 ms 16992 KB Output is correct
7 Correct 15 ms 16984 KB Output is correct
8 Correct 19 ms 16984 KB Output is correct
9 Correct 25 ms 17496 KB Output is correct
10 Correct 48 ms 17496 KB Output is correct
11 Correct 79 ms 17752 KB Output is correct
12 Correct 95 ms 18264 KB Output is correct
13 Correct 138 ms 18264 KB Output is correct
14 Correct 204 ms 18776 KB Output is correct
15 Correct 210 ms 21332 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1510 ms 22136 KB Output is correct
2 Correct 1783 ms 21680 KB Output is correct
3 Correct 2406 ms 23896 KB Output is correct
4 Correct 213 ms 19032 KB Output is correct
5 Correct 259 ms 20312 KB Output is correct
6 Correct 454 ms 22488 KB Output is correct
7 Correct 1256 ms 22252 KB Output is correct
8 Correct 826 ms 31568 KB Output is correct
9 Correct 1867 ms 26960 KB Output is correct
10 Correct 2858 ms 38860 KB Output is correct
11 Correct 3384 ms 30688 KB Output is correct
12 Correct 1118 ms 29372 KB Output is correct
13 Correct 1473 ms 30384 KB Output is correct
14 Correct 1878 ms 32100 KB Output is correct
15 Correct 2589 ms 34684 KB Output is correct
16 Correct 2552 ms 41780 KB Output is correct
17 Correct 2297 ms 41936 KB Output is correct