oj.uz

Submission #777344

# Submission time Handle Problem Language Result Execution time Memory
777344 2023-07-09T06:21:27 Z ETO_leader Regions (IOI09_regions) C++17
6 / 100
 6022 ms 131072 KB 
#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using VI=vector<int>;
vector<VI> G,cx,ck;
VI tin,tout,vis,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 id,int f=0){
    if(vis[u]) return;
    vis[u]=true;cx[id][col[u]]++;
    for(auto&i:G[u]) if(i!=f) dfsx(i,id,u);
}
void init(int n){
    G.resize(n+1);tin.resize(n+1);col.resize(n+1);
    tout.resize(n+1);vis.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=pow<double>(n,3.0/1.0)+1;
    VI 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(col[i]>sqr){
        idx[i]=cx.size();cx.push_back(VI(r+1));
        fill(vis.begin(),vis.end(),false);
        for(auto&j:ci[i]) dfsx(j,idx[i]);
        ck.push_back(VI(r+1));
        cir(j,1,r+1) ck[idx[i]][j]=cnx[j]-cx[idx[i]][j];
    }
    auto bfdis=[&](int c1,int c2){
        int res=0;
        for(auto&i:ci[c1]) for(auto&j:ci[c2]){
            res+=isancestor(i,j);
        }
        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;
}

Subtask #1
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 6 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 16 ms 336 KB Output is correct
7 Incorrect 11 ms 592 KB Output isn't correct
8 Incorrect 31 ms 720 KB Output isn't correct
9 Incorrect 37 ms 1744 KB Output isn't correct
10 Incorrect 109 ms 2584 KB Output isn't correct
11 Incorrect 139 ms 2044 KB Output isn't correct
12 Incorrect 205 ms 3812 KB Output isn't correct
13 Incorrect 258 ms 3144 KB Output isn't correct
14 Incorrect 220 ms 3052 KB Output isn't correct
15 Incorrect 210 ms 6560 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 856 ms 7644 KB Output isn't correct
2 Incorrect 811 ms 7340 KB Output isn't correct
3 Incorrect 1224 ms 10212 KB Output isn't correct
4 Incorrect 2466 ms 128656 KB Output isn't correct
5 Runtime error 787 ms 131072 KB Execution killed with signal 9
6 Runtime error 2257 ms 131072 KB Execution killed with signal 9
7 Runtime error 2478 ms 131072 KB Execution killed with signal 9
8 Runtime error 1589 ms 131072 KB Execution killed with signal 9
9 Runtime error 3135 ms 131072 KB Execution killed with signal 9
10 Runtime error 1398 ms 131072 KB Execution killed with signal 9
11 Runtime error 2988 ms 131072 KB Execution killed with signal 9
12 Runtime error 6022 ms 131072 KB Execution killed with signal 9
13 Runtime error 3808 ms 131072 KB Execution killed with signal 9
14 Runtime error 4927 ms 131072 KB Execution killed with signal 9
15 Runtime error 2431 ms 131072 KB Execution killed with signal 9
16 Runtime error 1864 ms 131072 KB Execution killed with signal 9
17 Runtime error 1996 ms 131072 KB Execution killed with signal 9