oj.uz

Submission #777390

# Submission time Handle Problem Language Result Execution time Memory
777390 2023-07-09T07:47:29 Z ETO_leader Regions (IOI09_regions) C++17
100 / 100
 2122 ms 33868 KB 
#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
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)*4)+1;
    VL cnx(r+1),idx(n+1);
    vector<VI> ci(r+1),ex(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];
        }else{
            for(auto&j:ci[i]){
                ex[i].push_back(tin[j]);
                ex[i].push_back(-tout[j]-1);
            }
            sort(ex[i].begin(),ex[i].end(),
                [&](int a,int b){return abs(a)<abs(b);});
            sort(ci[i].begin(),ci[i].end(),
                [&](int a,int b){return tin[a]<tin[b];});
        }
    }
    auto bfdis=[&](int c1,int c2){
        lint res=0,pre=0,p=0;
        for(auto&i:ci[c2]){
            while(p<ex[c1].size()){
                const int vx=ex[c1][p];
                if(abs(vx)>tin[i]) break;
                pre+=(vx<0?-1:1);++p;
            }
            res+=pre;
        }
        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 lambda function:
regions.cpp:64:20: warning: comparison of integer expressions of different signedness: 'lint' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             while(p<ex[c1].size()){
      |                   ~^~~~~~~~~~~~~~

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 6 ms 336 KB Output is correct
6 Correct 16 ms 336 KB Output is correct
7 Correct 24 ms 464 KB Output is correct
8 Correct 22 ms 464 KB Output is correct
9 Correct 38 ms 1104 KB Output is correct
10 Correct 44 ms 1232 KB Output is correct
11 Correct 84 ms 1788 KB Output is correct
12 Correct 108 ms 2516 KB Output is correct
13 Correct 104 ms 2772 KB Output is correct
14 Correct 156 ms 3308 KB Output is correct
15 Correct 165 ms 6652 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 8248 KB Output is correct
2 Correct 854 ms 8008 KB Output is correct
3 Correct 1174 ms 10736 KB Output is correct
4 Correct 192 ms 3676 KB Output is correct
5 Correct 244 ms 5756 KB Output is correct
6 Correct 610 ms 6056 KB Output is correct
7 Correct 593 ms 8092 KB Output is correct
8 Correct 827 ms 14832 KB Output is correct
9 Correct 1135 ms 17396 KB Output is correct
10 Correct 1496 ms 24272 KB Output is correct
11 Correct 1978 ms 21836 KB Output is correct
12 Correct 810 ms 19752 KB Output is correct
13 Correct 1014 ms 20764 KB Output is correct
14 Correct 1423 ms 21616 KB Output is correct
15 Correct 2122 ms 26648 KB Output is correct
16 Correct 1687 ms 33868 KB Output is correct
17 Correct 1782 ms 32248 KB Output is correct