oj.uz

Submission #895313

# Submission time Handle Problem Language Result Execution time Memory
895313 2023-12-29T18:39:32 Z ilef Regions (IOI09_regions) C++14
0 / 100
 119 ms 131072 KB 
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+12;
const int R=501;
int H[N];
vector<int>graph[N];
vector<int>v[R];
int id[N];
int sz[R][N];
int trav[R][N];
void dfs(int u,int r2,int p,int &cnt){
    id[u]=cnt;
     sz[r2][u]=1;
    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);
            sz[r2][u]+=sz[r2][v];
        }
    }
}
struct segtree{
    int size;
    vector<vector<int>>sums;
    void init(int n){
        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);
        }
    vector<vector<int>>val(r,vector<int>(R,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);
    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[r2][u];
            //cout<<szz<<endl;
            summ+=st.sum(a,a+szz+1,r2);
        }
        cout<<summ<<endl;
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 21080 KB Output isn't correct
2 Incorrect 5 ms 29272 KB Output isn't correct
3 Incorrect 14 ms 70644 KB Output isn't correct
4 Incorrect 18 ms 119588 KB Output isn't correct
5 Runtime error 20 ms 131072 KB Execution killed with signal 9
6 Runtime error 21 ms 131072 KB Execution killed with signal 9
7 Runtime error 24 ms 131072 KB Execution killed with signal 9
8 Runtime error 23 ms 131072 KB Execution killed with signal 9
9 Runtime error 48 ms 131072 KB Execution killed with signal 9
10 Runtime error 30 ms 131072 KB Execution killed with signal 9
11 Runtime error 39 ms 131072 KB Execution killed with signal 9
12 Runtime error 44 ms 131072 KB Execution killed with signal 9
13 Runtime error 49 ms 131072 KB Execution killed with signal 9
14 Runtime error 88 ms 131072 KB Execution killed with signal 9
15 Runtime error 56 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 110 ms 131072 KB Execution killed with signal 9
2 Runtime error 119 ms 131072 KB Execution killed with signal 9
3 Runtime error 97 ms 131072 KB Execution killed with signal 9
4 Runtime error 30 ms 6488 KB Execution killed with signal 11
5 Runtime error 33 ms 6488 KB Execution killed with signal 11
6 Runtime error 31 ms 6488 KB Execution killed with signal 11
7 Runtime error 30 ms 6488 KB Execution killed with signal 11
8 Runtime error 31 ms 6488 KB Execution killed with signal 11
9 Runtime error 30 ms 6488 KB Execution killed with signal 11
10 Runtime error 31 ms 6488 KB Execution killed with signal 11
11 Runtime error 32 ms 6488 KB Execution killed with signal 11
12 Runtime error 30 ms 6488 KB Execution killed with signal 11
13 Runtime error 31 ms 6644 KB Execution killed with signal 11
14 Runtime error 30 ms 6488 KB Execution killed with signal 11
15 Runtime error 30 ms 6488 KB Execution killed with signal 11
16 Runtime error 30 ms 6488 KB Execution killed with signal 11
17 Runtime error 30 ms 6740 KB Execution killed with signal 11