oj.uz

Submission #895349

# Submission time Handle Problem Language Result Execution time Memory
895349 2023-12-29T19:19:47 Z ilef Regions (IOI09_regions) C++14
9 / 100
 195 ms 131072 KB 
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=25001;
const int R=501;
int H[N];
vector<int>graph[N];
vector<int>v[R];
int id[N];
int sz[N];
int trav[R][N];
void dfs(int u,int r2,int p,int &cnt){
    if(H[u]==r2){
       
        trav[r2][cnt]=1;
    }
    else{
         trav[r2][cnt]=0;
    }
     cnt++;
    for(auto v:graph[u]){
        if(v!=p){
            dfs(v,r2,u,cnt);
        }
    }
}
void dfs1(int u,int p,int &cnt){
    id[u]=cnt;
     sz[u]=1;
     cnt++;
    for(auto v:graph[u]){
        if(v!=p){
            dfs1(v,u,cnt);
            sz[u]+=sz[v];
        }
    }
}
struct segtree{
    int size;
    vector<vector<int>>sums;
    void init(int n,int r){
        size=1;
        while(size<n){
            size*=2;
        }
        sums.assign(r,vector<int>(2*size,0LL));
    }
     void build(vector<vector<int>>&a,int x,int lx,int rx,int r){
        if(rx-lx==1){
            if(lx<(int)a[r].size()){
               sums[r][x]=a[r][lx];
            }
            return ;
        }
        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m,r);
        build(a,2*x+2,m,rx,r);
        sums[r][x]=sums[r][2*x+1]+sums[r][2*x+2];
    }
    void build(vector<vector<int>>&a,int r){
        build(a,0,0,size,r);
    }
    void set(int i,int v,int x,int lx,int rx,int r){
        if(rx-lx==1){
            sums[r][x]=v;
            return ;
        }
        int m=(lx+rx)/2;
        if(i<m){
            set(i,v,2*x+1,lx,m,r);
        }
        else{
            set(i,v,2*x+2,m,rx,r);
        }
        sums[r][x]=sums[r][2*x+1]+sums[r][2*x+2];
    }
     void set(int i,int v,int r){
        set(i,v,0,0,size, r);
    }
    long long sum(int l,int r,int x,int lx,int rx,int rr){
        if(lx>=r || l>=rx){
            return 0;
        }
        if(lx>=l && rx<=r){
            return sums[rr][x];
        }
        int m=(lx+rx)/2;
        return sum(l,r,2*x+1,lx,m,rr)+sum(l,r,2*x+2,m,rx,rr);
    }
    long long sum(int l,int r,int rr){
        return sum(l,r,0,0,size,rr);
    }
};
int32_t main(){
    int n,r,q;
    cin>>n>>r>>q;
    cin>>H[0];
    H[0]--;
    v[H[0]].push_back(0);
    for(int i=1;i<=n-1;i++){
        //cout<<1<<endl;
        int u;
        cin>>u>>H[i];
        H[i]--;
        u--;
        v[H[i]].push_back(i);
        graph[u].push_back(i);
        graph[i].push_back(u);
    }
        for(int j=0;j<r;j++){
            //cout<<1<<endl;
            int  cnt=0;
            dfs(0,j,-1,cnt);
        }
        int cnt=0;
        dfs1(0,-1,cnt);
    vector<vector<int>>val(r,vector<int>(n,0LL));
    for(int i=0;i<n;i++){
        for(int j=0;j<r;j++){
            val[j][i]=trav[j][i];
        }
    }
    segtree st;
    st.init(n,r);
    for(int j=0;j<r;j++){
        //cout<<1<<endl;
    st.build(val,j);}

    while(q--){
        //cout<<1<<endl;
        int r1,r2;
        cin>>r1>>r2;
       // cout<<endl;
        r1--;r2--;
        int summ=0;
        for(auto u:v[r1]){
            int a=id[u];
            int szz=sz[u];
            //cout<<szz<<endl;
            summ+=st.sum(a+1,a+szz,r2);
            
        }
        cout<<summ<<endl;
    }
}

Subtask #1
9.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 2 ms 7000 KB Output is correct
4 Correct 3 ms 11272 KB Output is correct
5 Correct 5 ms 13656 KB Output is correct
6 Correct 20 ms 57832 KB Output is correct
7 Correct 24 ms 40348 KB Output is correct
8 Correct 37 ms 51596 KB Output is correct
9 Correct 95 ms 114532 KB Output is correct
10 Runtime error 104 ms 131072 KB Execution killed with signal 9
11 Runtime error 121 ms 131072 KB Execution killed with signal 9
12 Runtime error 167 ms 131072 KB Execution killed with signal 9
13 Runtime error 195 ms 131072 KB Execution killed with signal 9
14 Runtime error 16 ms 7924 KB Execution killed with signal 11
15 Runtime error 16 ms 7848 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 7812 KB Execution killed with signal 11
2 Runtime error 19 ms 8284 KB Execution killed with signal 11
3 Runtime error 16 ms 7876 KB Execution killed with signal 11
4 Runtime error 4 ms 5464 KB Execution killed with signal 11
5 Runtime error 4 ms 5464 KB Execution killed with signal 11
6 Runtime error 5 ms 5464 KB Execution killed with signal 11
7 Runtime error 5 ms 5468 KB Execution killed with signal 11
8 Runtime error 5 ms 5340 KB Execution killed with signal 11
9 Runtime error 4 ms 5464 KB Execution killed with signal 11
10 Runtime error 5 ms 5300 KB Execution killed with signal 11
11 Runtime error 4 ms 5464 KB Execution killed with signal 11
12 Runtime error 4 ms 5464 KB Execution killed with signal 11
13 Runtime error 4 ms 5464 KB Execution killed with signal 11
14 Runtime error 5 ms 5464 KB Execution killed with signal 11
15 Runtime error 5 ms 5464 KB Execution killed with signal 11
16 Runtime error 5 ms 5464 KB Execution killed with signal 11
17 Runtime error 4 ms 5464 KB Execution killed with signal 11