oj.uz

Submission #1024988

# Submission time Handle Problem Language Result Execution time Memory
1024988 2024-07-16T13:44:04 Z MMihalev Regions (IOI09_regions) C++14
0 / 100
 217 ms 37584 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);
    }
}
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";
    }
    return 0;
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8 ms 15448 KB Time limit exceeded (wall clock)
2 Execution timed out 6 ms 15448 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 15448 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 15448 KB Time limit exceeded (wall clock)
5 Execution timed out 5 ms 15448 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 15448 KB Time limit exceeded (wall clock)
7 Execution timed out 6 ms 15448 KB Time limit exceeded (wall clock)
8 Execution timed out 6 ms 15448 KB Time limit exceeded (wall clock)
9 Execution timed out 7 ms 15960 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 15960 KB Time limit exceeded (wall clock)
11 Execution timed out 9 ms 16216 KB Time limit exceeded (wall clock)
12 Execution timed out 9 ms 16728 KB Time limit exceeded (wall clock)
13 Execution timed out 10 ms 16984 KB Time limit exceeded (wall clock)
14 Execution timed out 14 ms 17240 KB Time limit exceeded (wall clock)
15 Execution timed out 13 ms 19800 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 40 ms 20560 KB Time limit exceeded (wall clock)
2 Execution timed out 42 ms 20240 KB Time limit exceeded (wall clock)
3 Execution timed out 39 ms 22320 KB Time limit exceeded (wall clock)
4 Execution timed out 12 ms 17496 KB Time limit exceeded (wall clock)
5 Execution timed out 18 ms 18856 KB Time limit exceeded (wall clock)
6 Execution timed out 91 ms 21072 KB Time limit exceeded (wall clock)
7 Execution timed out 50 ms 21072 KB Time limit exceeded (wall clock)
8 Execution timed out 110 ms 29264 KB Time limit exceeded (wall clock)
9 Execution timed out 40 ms 25944 KB Time limit exceeded (wall clock)
10 Execution timed out 155 ms 36788 KB Time limit exceeded (wall clock)
11 Execution timed out 54 ms 28876 KB Time limit exceeded (wall clock)
12 Execution timed out 75 ms 27296 KB Time limit exceeded (wall clock)
13 Execution timed out 76 ms 28000 KB Time limit exceeded (wall clock)
14 Execution timed out 217 ms 30148 KB Time limit exceeded (wall clock)
15 Execution timed out 67 ms 31928 KB Time limit exceeded (wall clock)
16 Execution timed out 59 ms 37072 KB Time limit exceeded (wall clock)
17 Execution timed out 90 ms 37584 KB Time limit exceeded (wall clock)