oj.uz

Submission #1024993

# Submission time Handle Problem Language Result Execution time Memory
1024993 2024-07-16T13:49:44 Z MMihalev Regions (IOI09_regions) C++17
35 / 100
 3373 ms 36700 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";
        cout.flush();
    }
    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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 6 ms 14424 KB Output is correct
3 Correct 8 ms 14424 KB Output is correct
4 Correct 8 ms 14424 KB Output is correct
5 Correct 10 ms 14436 KB Output is correct
6 Correct 12 ms 14420 KB Output is correct
7 Correct 21 ms 14680 KB Output is correct
8 Correct 21 ms 14680 KB Output is correct
9 Correct 40 ms 14936 KB Output is correct
10 Correct 53 ms 15192 KB Output is correct
11 Correct 93 ms 15448 KB Output is correct
12 Correct 119 ms 16232 KB Output is correct
13 Correct 145 ms 15960 KB Output is correct
14 Correct 206 ms 16216 KB Output is correct
15 Correct 195 ms 18884 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1507 ms 19720 KB Output isn't correct
2 Incorrect 1753 ms 19480 KB Output isn't correct
3 Incorrect 2389 ms 21328 KB Output isn't correct
4 Correct 199 ms 16472 KB Output is correct
5 Correct 271 ms 17908 KB Output is correct
6 Incorrect 418 ms 20144 KB Output isn't correct
7 Incorrect 1204 ms 19972 KB Output isn't correct
8 Incorrect 831 ms 28496 KB Output isn't correct
9 Correct 1873 ms 25168 KB Output is correct
10 Incorrect 2828 ms 36068 KB Output isn't correct
11 Correct 3373 ms 28040 KB Output is correct
12 Incorrect 1101 ms 26572 KB Output isn't correct
13 Incorrect 1277 ms 27336 KB Output isn't correct
14 Incorrect 1798 ms 29392 KB Output isn't correct
15 Incorrect 2462 ms 31064 KB Output isn't correct
16 Incorrect 2461 ms 36304 KB Output isn't correct
17 Incorrect 2275 ms 36700 KB Output isn't correct