oj.uz

Submission #777352

# Submission time Handle Problem Language Result Execution time Memory
777352 2023-07-09T06:35:24 Z ETO_leader Regions (IOI09_regions) C++17
0 / 100
 7598 ms 131072 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();cx.push_back(VL(r+1));
        fill(w.begin(),w.end(),0);
        dfsx(1,i);
        cir(j,1,n+1) cx[idx[i]][col[j]]+=w[j];
    }
    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 0 ms 208 KB Unexpected end of file - int32 expected
4 Incorrect 0 ms 208 KB Unexpected end of file - int32 expected
5 Incorrect 1 ms 336 KB Unexpected end of file - int32 expected
6 Incorrect 0 ms 336 KB Unexpected end of file - int32 expected
7 Incorrect 3 ms 592 KB Unexpected end of file - int32 expected
8 Incorrect 5 ms 720 KB Unexpected end of file - int32 expected
9 Incorrect 14 ms 1744 KB Unexpected end of file - int32 expected
10 Incorrect 71 ms 2584 KB Unexpected end of file - int32 expected
11 Incorrect 77 ms 2120 KB Unexpected end of file - int32 expected
12 Incorrect 147 ms 3916 KB Unexpected end of file - int32 expected
13 Incorrect 172 ms 3312 KB Unexpected end of file - int32 expected
14 Incorrect 139 ms 3200 KB Unexpected end of file - int32 expected
15 Incorrect 91 ms 6608 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 7744 KB Unexpected end of file - int32 expected
2 Incorrect 343 ms 7564 KB Unexpected end of file - int32 expected
3 Incorrect 250 ms 10524 KB Unexpected end of file - int32 expected
4 Incorrect 2509 ms 128720 KB Unexpected end of file - int32 expected
5 Runtime error 1389 ms 131072 KB Execution killed with signal 9
6 Runtime error 2569 ms 131072 KB Execution killed with signal 9
7 Runtime error 2573 ms 131072 KB Execution killed with signal 9
8 Runtime error 1714 ms 131072 KB Execution killed with signal 9
9 Runtime error 3580 ms 131072 KB Execution killed with signal 9
10 Runtime error 1557 ms 131072 KB Execution killed with signal 9
11 Runtime error 3405 ms 131072 KB Execution killed with signal 9
12 Runtime error 7598 ms 131072 KB Execution killed with signal 9
13 Runtime error 5045 ms 131072 KB Execution killed with signal 9
14 Runtime error 5729 ms 131072 KB Execution killed with signal 9
15 Runtime error 2654 ms 131072 KB Execution killed with signal 9
16 Runtime error 2149 ms 131072 KB Execution killed with signal 9
17 Runtime error 2563 ms 131072 KB Execution killed with signal 9