oj.uz

Submission #427994

# Submission time Handle Problem Language Result Execution time Memory
427994 2021-06-15T06:55:21 Z 조영욱(#7659) Counterspells (CPSPC17_counterspells) C++17
0 / 100
 514 ms 27432 KB 
#include <bits/stdc++.h>
using namespace std;

int par[200001][18];
int n;
int ind[200001];
int sz[200001];
int dep[200001];
vector<int> son[200001];
int f=0;
const int INF=1e9;

void dfs(int v,int prev) {
    ind[v]=f++;
    sz[v]=1;
    par[v][0]=prev;
    for(int nt:son[v]) {
        dep[nt]=dep[v]+1;
        dfs(nt,v);
        sz[v]+=sz[nt];
    }
}

const int siz=262144;
int seg[siz*2];

int sum(int l,int r,int node=1,int nodel=0,int noder=siz-1) {
    if (r<nodel||l>noder) {
        return 1e9;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return min(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}

void update(int i,int val) {
    i+=siz;
    seg[i]=val;
    while (i>1) {
        i/=2;
        seg[i]=min(seg[i*2],seg[i*2+1]);
    }
}

int arr[200001];

int main(void) {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        int p;
        scanf("%d",&p);
        arr[i]=p;
        son[p].push_back(i);
    }
    memset(par,-1,sizeof(par));
    dfs(0,-1);
    for(int j=1;j<18;j++) {
        for(int i=0;i<=n;i++) {
            if (par[i][j-1]!=-1) {
                par[i][j]=par[par[i][j-1]][j-1];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        update(i,INF);
    }
    for(int i=1;i<=n;i++) {
        int now=i;
        update(ind[arr[i]],INF);
        for(int j=17;j>=0;j--){
            int nt=par[now][j];
            if (nt!=-1&&sum(ind[nt],ind[nt]+sz[nt]-1)>dep[i]) {
                now=nt;
            }
        }
        printf("%d\n",dep[i]-dep[now]);
        update(ind[i],dep[i]);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 514 ms 27432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 19148 KB Output isn't correct
2 Halted 0 ms 0 KB -