제출 #777383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777383		ETO_leader	Regions (IOI09_regions)	C++17	100 / 100	4861 ms	31652 KiB

regions

#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
template<typename T>
class bit{
private:
    vector<T> v;int n;
    int lowbit(int x) const{return x&(-x);}
public:
    void update(int p,T w){
        ++p;
        while(p<n) v[p]+=w,p+=lowbit(p);
    }
    T operator()(int p) const{
        T res=0;++p;
        while(p) res+=v[p],p-=lowbit(p);
        return res;
    }
    void resize(int _n){(*this)=bit(_n);}
    bit(int _n=0):n(_n),v(_n){}
};
using VI=vector<int>;
using VL=vector<lint>;
vector<VI> G;vector<VL> cx,ck;
VI tin,tout,w,col;
void dfs(int u,int&cnx,int f=0){
    tin[u]=++cnx;
    for(auto&i:G[u]) if(i!=f) dfs(i,cnx,u);
    tout[u]=cnx;
}
bool isancestor(int u,int v){
    return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
void dfsx(int u,int ci,int wx=0,int f=0){
    w[u]=(wx+=(col[u]==ci));
    for(auto&i:G[u]) if(i!=f) dfsx(i,ci,wx,u);
}
void init(int n){
    G.resize(n+1);tin.resize(n+1);col.resize(n+1);
    tout.resize(n+1);w.resize(n+1);
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,r,q;cin>>n>>r>>q;init(n);
    const int sqr=sqrt(n*log2(n)*2)+1;
    VL cnx(r+1),idx(n+1);
    vector<VI> ci(r+1);
    cin>>col[1];cnx[col[1]]++;ci[col[1]].push_back(1);
    cir(i,2,n+1){
        int f;cin>>f>>col[i];cnx[col[i]]++;
        G[f].push_back(i);G[i].push_back(f);
        ci[col[i]].push_back(i);
    }
    [&](){int ncnx=0;dfs(1,ncnx);}();
    cir(i,1,r+1) if(cnx[i]>sqr){
        idx[i]=cx.size();cx.push_back(VL(r+1));
        fill(w.begin(),w.end(),0);
        dfsx(1,i);
        cir(j,1,n+1) cx[idx[i]][col[j]]+=w[j];
        ck.push_back(VL(r+1));
        VI cw(n+7);
        for(auto&j:ci[i]) cw[tin[j]]++;
        cir(i,1,n+1) cw[i]+=cw[i-1];
        cir(j,1,n+1)
            ck[idx[i]][col[j]]+=cw[tout[j]]-cw[tin[j]-1];
    }
    bit<int> bx(n+7);
    auto bfdis=[&](int c1,int c2){
        lint res=0;
        for(auto&i:ci[c2]) bx.update(tin[i],1);
        for(auto&i:ci[c1]) res+=bx(tout[i])-bx(tin[i]-1);
        for(auto&i:ci[c2]) bx.update(tin[i],-1);
        return res;
    };
    cir(i,0,q){
        int r1,r2;cin>>r1>>r2;
        if(cnx[r1]>sqr) cout<<cx[idx[r1]][r2]<<'\n';
        else if(cnx[r2]>sqr) cout<<ck[idx[r2]][r1]<<'\n';
        else cout<<bfdis(r1,r2)<<'\n';
        cout.flush();
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

regions.cpp: In instantiation of 'bit<T>::bit(int) [with T = int]':
regions.cpp:68:20:   required from here
regions.cpp:8:21: warning: 'bit<int>::n' will be initialized after [-Wreorder]
    8 |     vector<T> v;int n;
      |                     ^
regions.cpp:8:15: warning:   'std::vector<int> bit<int>::v' [-Wreorder]
    8 |     vector<T> v;int n;
      |               ^
regions.cpp:21:5: warning:   when initialized here [-Wreorder]
   21 |     bit(int _n=0):n(_n),v(_n){}
      |     ^~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85