oj.uz

Submission #777393

# Submission time Handle Problem Language Result Execution time Memory
777393 2023-07-09T07:48:46 Z vjudge1 Regions (IOI09_regions) C++17
100 / 100
 2416 ms 33872 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 5 ms 208 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 7 ms 336 KB Output is correct
7 Correct 19 ms 464 KB Output is correct
8 Correct 29 ms 464 KB Output is correct
9 Correct 46 ms 1104 KB Output is correct
10 Correct 66 ms 1232 KB Output is correct
11 Correct 81 ms 1792 KB Output is correct
12 Correct 109 ms 2552 KB Output is correct
13 Correct 109 ms 2712 KB Output is correct
14 Correct 129 ms 3316 KB Output is correct
15 Correct 156 ms 6736 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 8252 KB Output is correct
2 Correct 962 ms 8012 KB Output is correct
3 Correct 1234 ms 10736 KB Output is correct
4 Correct 220 ms 3676 KB Output is correct
5 Correct 283 ms 5712 KB Output is correct
6 Correct 516 ms 6060 KB Output is correct
7 Correct 899 ms 8092 KB Output is correct
8 Correct 821 ms 14832 KB Output is correct
9 Correct 1406 ms 17392 KB Output is correct
10 Correct 1726 ms 24184 KB Output is correct
11 Correct 2416 ms 21832 KB Output is correct
12 Correct 767 ms 19752 KB Output is correct
13 Correct 1150 ms 20760 KB Output is correct
14 Correct 1459 ms 21616 KB Output is correct
15 Correct 1842 ms 26640 KB Output is correct
16 Correct 1613 ms 33872 KB Output is correct
17 Correct 1748 ms 32324 KB Output is correct