Submission #895323

# Submission time Handle Problem Language Result Execution time Memory
895323 2023-12-29T18:46:00 Z ilef Regions (IOI09_regions) C++14
Compilation error
0 ms 0 KB
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+12;
const int R=1001;
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,r2);
            if(r1==r2){
                summ--;
            }
        }
        cout<<summ<<endl;
    }
}

Compilation message

/tmp/ccahJdbD.o: in function `__tcf_0':
regions.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `graph' defined in .bss section in /tmp/ccahJdbD.o
/tmp/ccahJdbD.o: in function `__tcf_1':
regions.cpp:(.text+0x59): relocation truncated to fit: R_X86_64_PC32 against symbol `v' defined in .bss section in /tmp/ccahJdbD.o
/tmp/ccahJdbD.o: in function `dfs(long long, long long, long long, long long&)':
regions.cpp:(.text+0xac): relocation truncated to fit: R_X86_64_PC32 against symbol `id' defined in .bss section in /tmp/ccahJdbD.o
regions.cpp:(.text+0xe9): relocation truncated to fit: R_X86_64_PC32 against symbol `H' defined in .bss section in /tmp/ccahJdbD.o
regions.cpp:(.text+0x111): relocation truncated to fit: R_X86_64_PC32 against symbol `graph' defined in .bss section in /tmp/ccahJdbD.o
/tmp/ccahJdbD.o: in function `main':
regions.cpp:(.text.startup+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
regions.cpp:(.text.startup+0x5c): relocation truncated to fit: R_X86_64_PC32 against symbol `H' defined in .bss section in /tmp/ccahJdbD.o
regions.cpp:(.text.startup+0x63): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
regions.cpp:(.text.startup+0x6f): relocation truncated to fit: R_X86_64_PC32 against symbol `H' defined in .bss section in /tmp/ccahJdbD.o
regions.cpp:(.text.startup+0x76): relocation truncated to fit: R_X86_64_PC32 against symbol `v' defined in .bss section in /tmp/ccahJdbD.o
regions.cpp:(.text.startup+0x8d): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status