| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 895332 |
2023-12-29T18:58:09 Z |
ilef |
Regions (IOI09_regions) |
C++14 |
|
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>(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);
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/ccDrRtIa.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/ccDrRtIa.o
/tmp/ccDrRtIa.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/ccDrRtIa.o
/tmp/ccDrRtIa.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/ccDrRtIa.o
regions.cpp:(.text+0xe9): relocation truncated to fit: R_X86_64_PC32 against symbol `H' defined in .bss section in /tmp/ccDrRtIa.o
regions.cpp:(.text+0x111): relocation truncated to fit: R_X86_64_PC32 against symbol `graph' defined in .bss section in /tmp/ccDrRtIa.o
/tmp/ccDrRtIa.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+0x59): relocation truncated to fit: R_X86_64_PC32 against symbol `H' defined in .bss section in /tmp/ccDrRtIa.o
regions.cpp:(.text.startup+0x60): 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+0x6c): relocation truncated to fit: R_X86_64_PC32 against symbol `H' defined in .bss section in /tmp/ccDrRtIa.o
regions.cpp:(.text.startup+0x73): relocation truncated to fit: R_X86_64_PC32 against symbol `v' defined in .bss section in /tmp/ccDrRtIa.o
regions.cpp:(.text.startup+0x8a): 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
