oj.uz

Submission #777358

# Submission time Handle Problem Language Result Execution time Memory
777358 2023-07-09T06:55:56 Z ETO_leader Regions (IOI09_regions) C++17
55 / 100
 4781 ms 31264 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;
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))+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];
    }
    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<<cnx[r1]*cnx[r2]-cx[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:62: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 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 14 ms 336 KB Output is correct
7 Correct 19 ms 336 KB Output is correct
8 Correct 32 ms 464 KB Output is correct
9 Correct 45 ms 976 KB Output is correct
10 Correct 66 ms 1232 KB Output is correct
11 Correct 118 ms 1616 KB Output is correct
12 Correct 106 ms 2384 KB Output is correct
13 Correct 164 ms 2500 KB Output is correct
14 Correct 255 ms 3024 KB Output is correct
15 Correct 330 ms 6396 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1378 ms 7824 KB Output isn't correct
2 Incorrect 1135 ms 7580 KB Output isn't correct
3 Incorrect 2420 ms 10368 KB Output isn't correct
4 Correct 250 ms 3280 KB Output is correct
5 Correct 368 ms 5360 KB Output is correct
6 Correct 1336 ms 5544 KB Output is correct
7 Correct 1770 ms 7244 KB Output is correct
8 Correct 1748 ms 13860 KB Output is correct
9 Correct 3006 ms 15552 KB Output is correct
10 Correct 4738 ms 22120 KB Output is correct
11 Correct 4781 ms 19584 KB Output is correct
12 Incorrect 1368 ms 18112 KB Output isn't correct
13 Incorrect 1794 ms 19112 KB Output isn't correct
14 Incorrect 3221 ms 19628 KB Output isn't correct
15 Incorrect 3113 ms 23840 KB Output isn't correct
16 Incorrect 3473 ms 31264 KB Output isn't correct
17 Incorrect 3633 ms 29720 KB Output isn't correct