oj.uz

Submission #1004648

# Submission time Handle Problem Language Result Execution time Memory
1004648 2024-06-21T11:15:40 Z Mardonbekhazratov Regions (IOI09_regions) C++17
0 / 100
 233 ms 62920 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,dp;
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);
    for(int i=1;i<=r;i++){
        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+=S.get(tin[x],tout[x],r2);
            }
            cout<<ans<<'\n';
        }
    }
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
2 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
3 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
4 Execution timed out 0 ms 344 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
6 Execution timed out 1 ms 600 KB Time limit exceeded (wall clock)
7 Execution timed out 1 ms 600 KB Time limit exceeded (wall clock)
8 Execution timed out 1 ms 856 KB Time limit exceeded (wall clock)
9 Execution timed out 2 ms 1880 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 2904 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 3928 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 5976 KB Time limit exceeded (wall clock)
13 Execution timed out 10 ms 6228 KB Time limit exceeded (wall clock)
14 Execution timed out 20 ms 7512 KB Time limit exceeded (wall clock)
15 Execution timed out 17 ms 13140 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 52 ms 21704 KB Time limit exceeded (wall clock)
2 Execution timed out 51 ms 21456 KB Time limit exceeded (wall clock)
3 Execution timed out 41 ms 26056 KB Time limit exceeded (wall clock)
4 Execution timed out 12 ms 7512 KB Time limit exceeded (wall clock)
5 Execution timed out 18 ms 11732 KB Time limit exceeded (wall clock)
6 Execution timed out 79 ms 15240 KB Time limit exceeded (wall clock)
7 Execution timed out 108 ms 22196 KB Time limit exceeded (wall clock)
8 Execution timed out 111 ms 33424 KB Time limit exceeded (wall clock)
9 Execution timed out 80 ms 44232 KB Time limit exceeded (wall clock)
10 Execution timed out 196 ms 61480 KB Time limit exceeded (wall clock)
11 Execution timed out 85 ms 51660 KB Time limit exceeded (wall clock)
12 Execution timed out 101 ms 51656 KB Time limit exceeded (wall clock)
13 Execution timed out 97 ms 51940 KB Time limit exceeded (wall clock)
14 Execution timed out 233 ms 54236 KB Time limit exceeded (wall clock)
15 Execution timed out 87 ms 57548 KB Time limit exceeded (wall clock)
16 Execution timed out 105 ms 62920 KB Time limit exceeded (wall clock)
17 Execution timed out 126 ms 62544 KB Time limit exceeded (wall clock)