oj.uz

Submission #777340

# Submission time Handle Problem Language Result Execution time Memory
777340 2023-07-09T06:16:24 Z vjudge1 Regions (IOI09_regions) C++17
0 / 100
 6750 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];
    }
    cir(i,1,r+1) sort(ci[i].begin(),ci[i].end(),
        [&](int a,int b){return tin[a]<tin[b];});
    auto bfdis=[&](int c1,int c2){
        int res=0;
        unordered_set<int> ch;
        for(auto&i:ci[c1]) for(auto&j:ci[c2]){
            if(!ch.count(j)) res+=isancestor(i,j);
            if(isancestor(i,j)) ch.insert(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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Incorrect 1 ms 208 KB Output isn't correct
3 Incorrect 2 ms 208 KB Output isn't correct
4 Incorrect 3 ms 208 KB Output isn't correct
5 Incorrect 7 ms 336 KB Output isn't correct
6 Incorrect 15 ms 336 KB Output isn't correct
7 Incorrect 19 ms 592 KB Output isn't correct
8 Incorrect 19 ms 768 KB Output isn't correct
9 Incorrect 51 ms 1744 KB Output isn't correct
10 Incorrect 141 ms 2584 KB Output isn't correct
11 Incorrect 155 ms 2048 KB Output isn't correct
12 Incorrect 245 ms 3744 KB Output isn't correct
13 Incorrect 213 ms 3320 KB Output isn't correct
14 Incorrect 251 ms 3092 KB Output isn't correct
15 Incorrect 186 ms 6632 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 698 ms 7564 KB Output isn't correct
2 Incorrect 1012 ms 7216 KB Output isn't correct
3 Incorrect 1275 ms 10212 KB Output isn't correct
4 Incorrect 2397 ms 128552 KB Output isn't correct
5 Runtime error 759 ms 131072 KB Execution killed with signal 9
6 Runtime error 2268 ms 131072 KB Execution killed with signal 9
7 Runtime error 2474 ms 131072 KB Execution killed with signal 9
8 Runtime error 1698 ms 131072 KB Execution killed with signal 9
9 Runtime error 3633 ms 131072 KB Execution killed with signal 9
10 Runtime error 1371 ms 131072 KB Execution killed with signal 9
11 Runtime error 3416 ms 131072 KB Execution killed with signal 9
12 Runtime error 6750 ms 131072 KB Execution killed with signal 9
13 Runtime error 4148 ms 131072 KB Execution killed with signal 9
14 Runtime error 5300 ms 131072 KB Execution killed with signal 9
15 Runtime error 2747 ms 131072 KB Execution killed with signal 9
16 Runtime error 1827 ms 131072 KB Execution killed with signal 9
17 Runtime error 1963 ms 131072 KB Execution killed with signal 9