oj.uz

Submission #777355

# Submission time Handle Problem Language Result Execution time Memory
777355 2023-07-09T06:38:22 Z ETO_leader Regions (IOI09_regions) C++17
0 / 100
 8000 ms 30004 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);
        dfsx(1,i);
    }
    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 1 ms 208 KB Unexpected end of file - int32 expected
3 Incorrect 0 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 2 ms 336 KB Unexpected end of file - int32 expected
8 Incorrect 4 ms 464 KB Unexpected end of file - int32 expected
9 Incorrect 12 ms 976 KB Unexpected end of file - int32 expected
10 Incorrect 65 ms 1104 KB Unexpected end of file - int32 expected
11 Incorrect 75 ms 1616 KB Unexpected end of file - int32 expected
12 Incorrect 128 ms 2256 KB Unexpected end of file - int32 expected
13 Incorrect 164 ms 2368 KB Unexpected end of file - int32 expected
14 Incorrect 132 ms 2896 KB Unexpected end of file - int32 expected
15 Incorrect 80 ms 6224 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 221 ms 7516 KB Unexpected end of file - int32 expected
2 Incorrect 322 ms 7248 KB Unexpected end of file - int32 expected
3 Incorrect 260 ms 10016 KB Unexpected end of file - int32 expected
4 Incorrect 2352 ms 3152 KB Unexpected end of file - int32 expected
5 Incorrect 1713 ms 5212 KB Unexpected end of file - int32 expected
6 Incorrect 7231 ms 5328 KB Unexpected end of file - int32 expected
7 Execution timed out 8021 ms 6864 KB Time limit exceeded
8 Execution timed out 8069 ms 13384 KB Time limit exceeded
9 Execution timed out 8031 ms 14836 KB Time limit exceeded
10 Execution timed out 8037 ms 21320 KB Time limit exceeded
11 Execution timed out 8054 ms 18760 KB Time limit exceeded
12 Execution timed out 8074 ms 17004 KB Time limit exceeded
13 Execution timed out 8037 ms 18108 KB Time limit exceeded
14 Execution timed out 8055 ms 18396 KB Time limit exceeded
15 Execution timed out 8061 ms 22604 KB Time limit exceeded
16 Execution timed out 8041 ms 30004 KB Time limit exceeded
17 Execution timed out 8061 ms 28264 KB Time limit exceeded