oj.uz

Submission #428184

# Submission time Handle Problem Language Result Execution time Memory
428184 2021-06-15T08:42:19 Z 조영욱(#7659) Counterspells (CPSPC17_counterspells) C++17
40 / 100
 1000 ms 5412 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;
int tp[200001];

void dfs(int v,int prev) {
    sz[v]=1;
    par[v][0]=prev;
    for(int i=0;i<son[v].size();i++) {
        int nt=son[v][i];
        dep[nt]=dep[v]+1;
        dfs(nt,v);
        sz[v]+=sz[nt];
        if (sz[nt]>sz[son[v][0]]) {
            swap(son[v][0],son[v][i]);
        }
    }
}

void dfs_hld(int v) {
    ind[v]=f++;
    for(int i=0;i<son[v].size();i++) {
        int nt=son[v][i];
        tp[nt]=(i==0?tp[v]:nt);
        dfs_hld(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 INF;
    }
    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 seg1[siz*2];
int lazy[siz*2];

void propagate(int node,int nodel,int noder) {
    if (lazy[node]!=-1) {
        seg1[node]=lazy[node]*(noder-nodel+1);
        if (node<siz) {
            lazy[node*2]=lazy[node];
            lazy[node*2+1]=lazy[node];
        }
        lazy[node]=-1;
    }
}

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

void update1(int l,int r,int val,int node=1,int nodel=0,int noder=siz-1) {
    propagate(node,nodel,noder);
    if (r<nodel||l>noder) {
        return;
    }
    if (l<=nodel&&noder<=r) {
        lazy[node]=val;
        propagate(node,nodel,noder);
        return;
    }
    int mid=(nodel+noder)/2;
    update1(l,r,val,node*2,nodel,mid);
    update1(l,r,val,node*2+1,mid+1,noder);
    seg1[node]=seg1[node*2]+seg1[node*2+1];
}

int query(int u,int v) {
    bool flag=(u==0&&v==4);
    int ret=0;
    while (tp[v]!=tp[u]) {
        ret+=sum1(ind[tp[v]],ind[v]);
        if (flag){
            //printf("%d %d %d\n",ind[tp[v]],ind[v],sum1(ind[tp[v]],ind[v]));
        }
        v=par[tp[v]][0];
    }
    ret+=sum1(ind[u],ind[v]);
    return ret;
}

void upd(int u,int v,int val) {
    while (tp[v]!=tp[u]) {
        update1(ind[tp[v]],ind[v],val);
        v=par[tp[v]][0];
    }
    update1(ind[u],ind[v],val);
}

int arr[200001];

int main(void) {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        int p;
        scanf("%d",&p);
        son[p].push_back(i);
        int ret=0;
        for(int j=i;j>=0;j--) {
            bool flag=false;
            for(int k=0;k<son[j].size();k++) {
                if (arr[son[j][k]]==0) {
                    flag=true;
                }
            }
            if (flag) {
                if (arr[j]==0) {
                    ret++;
                }
                arr[j]=1;
            }
            else {
                if (arr[j]==1) {
                    ret++;
                }
                arr[j]=0;
            }
        }
        printf("%d\n",ret);
    }
}

Compilation message

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Main.cpp: In function 'void dfs_hld(int)':
Main.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=0;i<son[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:135:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |             for(int k=0;k<son[j].size();k++) {
      |                         ~^~~~~~~~~~~~~~
Main.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         scanf("%d",&p);
      |         ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 7 ms 5036 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 5 ms 4900 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 6 ms 4940 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 7 ms 5036 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 5 ms 4900 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 6 ms 4940 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 305 ms 5184 KB Output is correct
9 Correct 210 ms 5312 KB Output is correct
10 Correct 98 ms 5068 KB Output is correct
11 Correct 114 ms 5108 KB Output is correct
12 Correct 295 ms 5208 KB Output is correct
13 Correct 164 ms 5396 KB Output is correct
14 Correct 180 ms 5200 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 7 ms 5036 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 5 ms 4900 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 6 ms 4940 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 305 ms 5184 KB Output is correct
9 Correct 210 ms 5312 KB Output is correct
10 Correct 98 ms 5068 KB Output is correct
11 Correct 114 ms 5108 KB Output is correct
12 Correct 295 ms 5208 KB Output is correct
13 Correct 164 ms 5396 KB Output is correct
14 Correct 180 ms 5200 KB Output is correct
15 Execution timed out 1094 ms 5412 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 5240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4940 KB Output is correct
2 Correct 7 ms 5036 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 5 ms 4900 KB Output is correct
5 Correct 6 ms 4940 KB Output is correct
6 Correct 6 ms 4940 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 305 ms 5184 KB Output is correct
9 Correct 210 ms 5312 KB Output is correct
10 Correct 98 ms 5068 KB Output is correct
11 Correct 114 ms 5108 KB Output is correct
12 Correct 295 ms 5208 KB Output is correct
13 Correct 164 ms 5396 KB Output is correct
14 Correct 180 ms 5200 KB Output is correct
15 Execution timed out 1094 ms 5412 KB Time limit exceeded
16 Halted 0 ms 0 KB -