oj.uz

Submission #895351

# Submission time Handle Problem Language Result Execution time Memory
895351 2023-12-29T19:21:13 Z ilef Regions (IOI09_regions) C++14
5 / 100
 138 ms 131072 KB 
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=250001;
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
5.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 4 ms 24920 KB Output is correct
3 Correct 7 ms 51544 KB Output is correct
4 Correct 12 ms 80660 KB Output is correct
5 Correct 16 ms 99520 KB Output is correct
6 Runtime error 22 ms 131072 KB Execution killed with signal 9
7 Runtime error 24 ms 131072 KB Execution killed with signal 9
8 Runtime error 24 ms 131072 KB Execution killed with signal 9
9 Runtime error 24 ms 131072 KB Execution killed with signal 9
10 Runtime error 34 ms 131072 KB Execution killed with signal 9
11 Runtime error 63 ms 131072 KB Execution killed with signal 9
12 Runtime error 45 ms 131072 KB Execution killed with signal 9
13 Runtime error 54 ms 131072 KB Execution killed with signal 9
14 Runtime error 73 ms 131072 KB Execution killed with signal 9
15 Runtime error 53 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 124 ms 131072 KB Execution killed with signal 9
2 Runtime error 138 ms 131072 KB Execution killed with signal 9
3 Runtime error 105 ms 131072 KB Execution killed with signal 9
4 Runtime error 20 ms 8536 KB Execution killed with signal 11
5 Runtime error 19 ms 8536 KB Execution killed with signal 11
6 Runtime error 20 ms 8536 KB Execution killed with signal 11
7 Runtime error 19 ms 8536 KB Execution killed with signal 11
8 Runtime error 20 ms 8536 KB Execution killed with signal 11
9 Runtime error 19 ms 8536 KB Execution killed with signal 11
10 Runtime error 19 ms 8536 KB Execution killed with signal 11
11 Runtime error 20 ms 8536 KB Execution killed with signal 11
12 Runtime error 20 ms 8532 KB Execution killed with signal 11
13 Runtime error 20 ms 8536 KB Execution killed with signal 11
14 Runtime error 20 ms 8536 KB Execution killed with signal 11
15 Runtime error 20 ms 8536 KB Execution killed with signal 11
16 Runtime error 19 ms 8788 KB Execution killed with signal 11
17 Runtime error 20 ms 8536 KB Execution killed with signal 11