oj.uz

Submission #1004645

# Submission time Handle Problem Language Result Execution time Memory
1004645 2024-06-21T11:11:49 Z Mardonbekhazratov Regions (IOI09_regions) C++17
60 / 100
 8000 ms 62924 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>>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:120:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  120 |         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 7 ms 344 KB Output is correct
6 Correct 12 ms 600 KB Output is correct
7 Correct 19 ms 600 KB Output is correct
8 Correct 32 ms 852 KB Output is correct
9 Correct 69 ms 2128 KB Output is correct
10 Correct 95 ms 3152 KB Output is correct
11 Correct 232 ms 4220 KB Output is correct
12 Correct 363 ms 5980 KB Output is correct
13 Correct 248 ms 6096 KB Output is correct
14 Correct 589 ms 7592 KB Output is correct
15 Correct 1606 ms 13056 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 6446 ms 21876 KB Output is correct
2 Correct 4524 ms 21448 KB Output is correct
3 Execution timed out 8082 ms 26056 KB Time limit exceeded
4 Correct 759 ms 7704 KB Output is correct
5 Correct 1168 ms 11732 KB Output is correct
6 Correct 509 ms 15180 KB Output is correct
7 Correct 2646 ms 22396 KB Output is correct
8 Correct 3255 ms 33516 KB Output is correct
9 Execution timed out 8073 ms 44228 KB Time limit exceeded
10 Execution timed out 8071 ms 61384 KB Time limit exceeded
11 Execution timed out 8061 ms 51656 KB Time limit exceeded
12 Correct 4516 ms 51852 KB Output is correct
13 Execution timed out 8007 ms 51908 KB Time limit exceeded
14 Correct 6976 ms 54068 KB Output is correct
15 Execution timed out 8074 ms 57288 KB Time limit exceeded
16 Execution timed out 8055 ms 62924 KB Time limit exceeded
17 Execution timed out 8076 ms 62416 KB Time limit exceeded