제출 #895345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895345		ilef	Regions (IOI09_regions)	C++14	5 / 100	4 ms	1232 KiB

regions

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=501;
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 / 15
• Subtask 2: 0 / 85