oj.uz

Submission #777383

# Submission time Handle Problem Language Result Execution time Memory
777383 2023-07-09T07:35:39 Z ETO_leader Regions (IOI09_regions) C++17
100 / 100
 4861 ms 31652 KB 
#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;
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 18 ms 336 KB Output is correct
7 Correct 20 ms 336 KB Output is correct
8 Correct 25 ms 464 KB Output is correct
9 Correct 38 ms 976 KB Output is correct
10 Correct 71 ms 1232 KB Output is correct
11 Correct 98 ms 1616 KB Output is correct
12 Correct 117 ms 2384 KB Output is correct
13 Correct 157 ms 2492 KB Output is correct
14 Correct 258 ms 3024 KB Output is correct
15 Correct 252 ms 6400 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1273 ms 7828 KB Output is correct
2 Correct 1591 ms 7572 KB Output is correct
3 Correct 2303 ms 10396 KB Output is correct
4 Correct 341 ms 3288 KB Output is correct
5 Correct 385 ms 5368 KB Output is correct
6 Correct 1251 ms 5532 KB Output is correct
7 Correct 1911 ms 7248 KB Output is correct
8 Correct 1612 ms 13860 KB Output is correct
9 Correct 3043 ms 15560 KB Output is correct
10 Correct 4738 ms 22120 KB Output is correct
11 Correct 4861 ms 19592 KB Output is correct
12 Correct 1448 ms 18364 KB Output is correct
13 Correct 1765 ms 19372 KB Output is correct
14 Correct 3492 ms 19932 KB Output is correct
15 Correct 3253 ms 24232 KB Output is correct
16 Correct 3365 ms 31652 KB Output is correct
17 Correct 4019 ms 30104 KB Output is correct