제출 #1024997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024997		MMihalev	Regions (IOI09_regions)	C++14	100 / 100	3384 ms	41936 KiB

regions

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 85 / 85