oj.uz

Submission #777341

# Submission time Handle Problem Language Result Execution time Memory
777341 2023-07-09T06:17:29 Z ETO_leader Regions (IOI09_regions) C++17
0 / 100
 6943 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 0 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 4 ms 208 KB Output isn't correct
5 Incorrect 5 ms 336 KB Output isn't correct
6 Incorrect 13 ms 336 KB Output isn't correct
7 Incorrect 27 ms 632 KB Output isn't correct
8 Incorrect 25 ms 720 KB Output isn't correct
9 Incorrect 50 ms 1744 KB Output isn't correct
10 Incorrect 132 ms 2592 KB Output isn't correct
11 Incorrect 127 ms 2168 KB Output isn't correct
12 Incorrect 191 ms 3784 KB Output isn't correct
13 Incorrect 275 ms 3236 KB Output isn't correct
14 Incorrect 261 ms 3120 KB Output isn't correct
15 Incorrect 186 ms 6516 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 727 ms 7580 KB Output isn't correct
2 Incorrect 1006 ms 7332 KB Output isn't correct
3 Incorrect 1144 ms 10212 KB Output isn't correct
4 Incorrect 2345 ms 128652 KB Output isn't correct
5 Runtime error 707 ms 131072 KB Execution killed with signal 9
6 Runtime error 2172 ms 131072 KB Execution killed with signal 9
7 Runtime error 2504 ms 131072 KB Execution killed with signal 9
8 Runtime error 1551 ms 131072 KB Execution killed with signal 9
9 Runtime error 3508 ms 131072 KB Execution killed with signal 9
10 Runtime error 1337 ms 131072 KB Execution killed with signal 9
11 Runtime error 3350 ms 131072 KB Execution killed with signal 9
12 Runtime error 6943 ms 131072 KB Execution killed with signal 9
13 Runtime error 4034 ms 131072 KB Execution killed with signal 9
14 Runtime error 5075 ms 131072 KB Execution killed with signal 9
15 Runtime error 2922 ms 131072 KB Execution killed with signal 9
16 Runtime error 1988 ms 131072 KB Execution killed with signal 9
17 Runtime error 2037 ms 131072 KB Execution killed with signal 9