oj.uz

Submission #777354

# Submission time Handle Problem Language Result Execution time Memory
777354 2023-07-09T06:37:17 Z ETO_leader Regions (IOI09_regions) C++17
0 / 100
 367 ms 30096 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;
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=pow<double>(n,3.0/1.0)+1;
    VL 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(cnx[i]>sqr){
        idx[i]=cx.size();
        fill(w.begin(),w.end(),0);
    }
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Unexpected end of file - int32 expected
2 Incorrect 0 ms 208 KB Unexpected end of file - int32 expected
3 Incorrect 1 ms 208 KB Unexpected end of file - int32 expected
4 Incorrect 0 ms 208 KB Unexpected end of file - int32 expected
5 Incorrect 0 ms 336 KB Unexpected end of file - int32 expected
6 Incorrect 0 ms 336 KB Unexpected end of file - int32 expected
7 Incorrect 1 ms 336 KB Unexpected end of file - int32 expected
8 Incorrect 1 ms 464 KB Unexpected end of file - int32 expected
9 Incorrect 2 ms 976 KB Unexpected end of file - int32 expected
10 Incorrect 3 ms 1104 KB Unexpected end of file - int32 expected
11 Incorrect 5 ms 1612 KB Unexpected end of file - int32 expected
12 Incorrect 5 ms 2256 KB Unexpected end of file - int32 expected
13 Incorrect 9 ms 2404 KB Unexpected end of file - int32 expected
14 Incorrect 9 ms 2856 KB Unexpected end of file - int32 expected
15 Incorrect 10 ms 6252 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 7504 KB Unexpected end of file - int32 expected
2 Incorrect 24 ms 7124 KB Unexpected end of file - int32 expected
3 Incorrect 20 ms 9984 KB Unexpected end of file - int32 expected
4 Incorrect 12 ms 3168 KB Unexpected end of file - int32 expected
5 Incorrect 17 ms 5232 KB Unexpected end of file - int32 expected
6 Incorrect 27 ms 5328 KB Unexpected end of file - int32 expected
7 Incorrect 46 ms 6888 KB Unexpected end of file - int32 expected
8 Incorrect 66 ms 13468 KB Unexpected end of file - int32 expected
9 Incorrect 155 ms 14920 KB Unexpected end of file - int32 expected
10 Incorrect 285 ms 21424 KB Unexpected end of file - int32 expected
11 Incorrect 331 ms 18780 KB Unexpected end of file - int32 expected
12 Incorrect 220 ms 16996 KB Unexpected end of file - int32 expected
13 Incorrect 228 ms 18000 KB Unexpected end of file - int32 expected
14 Incorrect 285 ms 18412 KB Unexpected end of file - int32 expected
15 Incorrect 367 ms 22660 KB Unexpected end of file - int32 expected
16 Incorrect 338 ms 30096 KB Unexpected end of file - int32 expected
17 Incorrect 280 ms 28372 KB Unexpected end of file - int32 expected