oj.uz

Submission #1004653

# Submission time Handle Problem Language Result Execution time Memory
1004653 2024-06-21T11:30:12 Z Mardonbekhazratov Regions (IOI09_regions) C++17
100 / 100
 3195 ms 30536 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 12 ms 344 KB Output is correct
8 Correct 18 ms 600 KB Output is correct
9 Correct 29 ms 856 KB Output is correct
10 Correct 52 ms 1112 KB Output is correct
11 Correct 80 ms 1580 KB Output is correct
12 Correct 107 ms 2136 KB Output is correct
13 Correct 134 ms 2096 KB Output is correct
14 Correct 217 ms 2860 KB Output is correct
15 Correct 204 ms 5684 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1479 ms 7144 KB Output is correct
2 Correct 1745 ms 6088 KB Output is correct
3 Correct 2313 ms 9332 KB Output is correct
4 Correct 194 ms 3100 KB Output is correct
5 Correct 272 ms 4816 KB Output is correct
6 Correct 445 ms 6744 KB Output is correct
7 Correct 931 ms 8748 KB Output is correct
8 Correct 846 ms 16536 KB Output is correct
9 Correct 1920 ms 14392 KB Output is correct
10 Correct 2201 ms 30536 KB Output is correct
11 Correct 3195 ms 16344 KB Output is correct
12 Correct 1094 ms 17176 KB Output is correct
13 Correct 1462 ms 17380 KB Output is correct
14 Correct 1769 ms 19264 KB Output is correct
15 Correct 2400 ms 22464 KB Output is correct
16 Correct 2410 ms 27740 KB Output is correct
17 Correct 2306 ms 27880 KB Output is correct