Submission #1004653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004653		Mardonbekhazratov	Regions (IOI09_regions)	C++17	100 / 100	3195 ms	30536 KiB

regions

#include<bits/stdc++.h>
using namespace std;

struct mergeSortTree{
    int N,n;
    vector<vector<int>>tree;

    void build(int v,int l,int r,vector<int>&a){
        if(l>=n) return;
        if(r-l==1){
            tree[v]={a[l]};
            return;
        }

        int mid=(l+r)/2;
        build(v<<1,l,mid,a);
        build(v<<1|1,mid,r,a);
        merge(tree[v<<1].begin(),tree[v<<1].end(),tree[v<<1|1].begin(),tree[v<<1|1].end(),back_inserter(tree[v]));
    }

    mergeSortTree(vector<int>&a){
        n=(int)a.size();
        N=1;
        while(N<n) N<<=1;
        tree.resize(2*N);
        build(1,0,N,a);
    }

    // void update(int v,int l,int r,int id,int x){
    //     cout<<v;
    //     if(r-l==1){
    //         tree[v]+=x;
    //         return;
    //     }

    //     int mid=(l+r)/2;

    //     if(mid>id) update(v<<1,l,mid,id,x);
    //     else update(v<<1|1,mid,r,id,x);

    //     tree[v]=tree[v<<1]+tree[v<<1|1];
    // }

    // void update(int id,int x){
    //     return update(1,0,N,id,x);
    // }

    int get(int v,int l,int r,int ql,int qr,int x){
        if(ql>=r || l>=qr) return 0;
        if(l>=ql && qr>=r) return lower_bound(tree[v].begin(),tree[v].end(),x+1)-lower_bound(tree[v].begin(),tree[v].end(),x);
        
        int mid=(l+r)/2;

        return get(v<<1,l,mid,ql,qr,x)+get(v<<1|1,mid,r,ql,qr,x);
    }

    int get(int l,int r,int x){
        return get(1,0,N,l,r,x);
    }
};

int n,r,q,timer = 0;
vector<int>h,tin,tout,b,r_id;
vector<vector<int>>v,a,k;
vector<vector<int>>calc;

void dfs(int x){
    tin[x]=timer++;
    b.push_back(h[x]);
    for(int z:v[x]){
        dfs(z);
    }
    tout[x]=timer;
}

void dfs1(int x,int p_id,int p_c){
    calc[r_id[p_id]][h[x]]+=p_c;
    if(h[x]==p_id) p_c++;
    for(int z:v[x]){
        dfs1(z,p_id,p_c);
    }
}

/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
*/

signed main(){
    // cin.tie(0)->sync_with_stdio(0);
    cin>>n>>r>>q;
    h.resize(n+1);
    a.resize(r+1);
    cin>>h[1];
    v.assign(n+1,vector<int>(0));
    // dp.assign(r+1,vector<int>(r+1,-1));
    for(int i=2,x;i<=n;i++){
        cin>>x>>h[i];
        v[x].push_back(i);
    }
    for(int i=1;i<=n;i++){
        a[h[i]].push_back(i);
    }
    tin.resize(n+1);
    tout.resize(n+1);
    dfs(1);
    // mergeSortTree S(b);
    r_id.assign(r+1,-1);
    int cur=-1;
    const int BLOCK=(int)sqrt(n);
    k.resize(r+1);
    for(int i=1;i<=r;i++){
        for(int x:a[i]) k[i].push_back(tin[x]);
        sort(k[i].begin(),k[i].end());
        if(a[i].size()>=BLOCK){
            r_id[i]=++cur;
            calc.push_back(vector<int>(r+1));
            dfs1(1,i,0);
        }
    }
    while(q--){
        int r1,r2;
        cin>>r1>>r2;
        if(r_id[r1]>-1){
            cout<<calc[r_id[r1]][r2]<<'\n';
        }
        else{
            int ans=0;
            for(int x:a[r1]){
                ans+=lower_bound(k[r2].begin(),k[r2].end(),tout[x])-lower_bound(k[r2].begin(),k[r2].end(),tin[x]);
            }
            cout<<ans<<'\n';
        }
    }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:124:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  124 |         if(a[i].size()>=BLOCK){
      |            ~~~~~~~~~~~^~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85