oj.uz

Submission #427923

# Submission time Handle Problem Language Result Execution time Memory
427923 2021-06-15T05:15:46 Z 반딧불(#7617) Counterspells (CPSPC17_counterspells) C++17
20 / 100
 322 ms 71720 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

struct segTree{
    int *minTree, *maxTree, *lazy;

    segTree(int n){
        minTree = new int[4*n];
        maxTree = new int[4*n];
        lazy = new int[4*n];

        for(int i=0; i<4*n; i++) minTree[i] = maxTree[i] = lazy[i] = 0;
    }
    ~segTree(){
        delete[] minTree;
        delete[] maxTree;
        delete[] lazy;
    }

    void propagate(int i, int l, int r){
        minTree[i] += lazy[i];
        maxTree[i] += lazy[i];
        if(l!=r){
            lazy[i*2] += lazy[i];
            lazy[i*2+1] += lazy[i];
        }
        lazy[i] = 0;
    }

    void rangeAdd(int i, int l, int r, int s, int e, int val){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] = val;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        rangeAdd(i*2, l, m, s, e, val);
        rangeAdd(i*2+1, m+1, r, s, e, val);
        minTree[i] = min(minTree[i*2], minTree[i*2+1]);
        maxTree[i] = max(maxTree[i*2], maxTree[i*2+1]);
    }

    int lLim(int i, int l, int r, int x, int val){
        propagate(i, l, r);
        if(l>x) return l;
        if(minTree[i] == maxTree[i] && minTree[i] == val) return l;
        if(l==r) return l+1;
        int m = (l+r)>>1;
        if(x<=m) return lLim(i*2, l, m, x, val);
        int tmp = lLim(i*2+1, m+1, r, x, val);
        if(tmp != m+1) return tmp;
        return lLim(i*2, l, m, x, val);
    }

    pair<int, int> query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return make_pair(1000000000, -1000000000);
        if(s<=l && r<=e) return make_pair(minTree[i], maxTree[i]);
        int m = (l+r)>>1;
        pair<int, int> ret = query(i*2, l, m, s, e);
        pair<int, int> tmp = query(i*2+1, m+1, r, s, e);
        return make_pair(min(ret.first, tmp.first), max(ret.second, tmp.second));
    }
};

int n;
int par[200002];
vector<int> link[200002];
int in[200002], top[200002], sz[200002], len[200002], depth[200002], inCnt;
int L[200002][2], R[200002][2];
segTree *tree[200002][2];

void dfs_sz(int x){
    sz[x] = 1;
    for(auto &y: link[x]){
        depth[y] = depth[x]+1;
        dfs_sz(y);
        sz[y] += sz[x];
        if(sz[y] > sz[link[x][0]]) swap(y, link[x][0]);
    }
}

void dfs_hld(int x){
    in[x] = inCnt++;
    len[top[x]] = max(len[top[x]], in[x] - in[top[x]]);
    for(auto y: link[x]){
        top[y] = (y == link[x][0]) ? top[x] : y;
        dfs_hld(y);
    }
}

int main(){
    scanf("%d", &n);
    par[0] = -1;
    for(int i=1; i<=n; i++){
        scanf("%d", &par[i]);
        link[par[i]].push_back(i);
    }
    dfs_sz(0);
    dfs_hld(0);
    for(int i=0; i<=n; i++){
        if(top[i] == i){
            tree[i][0] = new segTree(len[i]/2+2); /// ���̰� ¦���� �������� ���׸�Ʈ Ʈ��
            tree[i][1] = new segTree(len[i]/2+2); /// ���̰� Ȧ���� �������� ���׸�Ʈ Ʈ��

            if(depth[i]%2){
                L[i][1] = (depth[i] - 1) / 2;
                R[i][1] = L[i][1] + len[i] / 2;

                L[i][0] = (depth[i] + 1) / 2;
                R[i][0] = L[i][0] + len[i] / 2;
            }
            else{
                L[i][0] = depth[i] / 2;
                R[i][0] = L[i][0] + len[i] / 2;

                L[i][1] = depth[i] / 2;
                R[i][1] = L[i][1] + len[i] / 2;
            }
        }
    }

    for(int i=1; i<=n; i++){
        int ans = 0;
        int x = par[i];
        int z0 = (depth[i] % 2) ? 0 : 1, z1 = !z0;
        int cnt = 0;

        while(x>=0){
            cnt++;
            int p = top[x];
            int l0 = tree[p][0]->lLim(1, L[p][0], R[p][0], depth[x]/2, z0);
            int l1 = tree[p][1]->lLim(1, L[p][1], R[p][1], (depth[x]+1)/2-1, z1);
            int lim = max(l0*2, l1*2+1)-1;
            ans += depth[x] - lim + 1;

            if(lim == depth[p]){
                tree[p][0]->rangeAdd(1, L[p][0], R[p][0], L[p][0], depth[x]/2, z1-z0);
                tree[p][1]->rangeAdd(1, L[p][1], R[p][1], L[p][1], (depth[x]+1)/2-1, z0-z1);
                x = par[p];
            }
            else{
                tree[p][0]->rangeAdd(1, L[p][0], R[p][0], (lim+1)/2, depth[x]/2, z1-z0);
                tree[p][1]->rangeAdd(1, L[p][1], R[p][1], lim/2, (depth[x]+1)/2-1, z0-z1);
                if(lim%2==0){
                    tree[p][1]->rangeAdd(1, L[p][1], R[p][1], (lim-1)/2, (lim-1)/2, z0-z1);
                }
                else{
                    tree[p][0]->rangeAdd(1, L[p][0], R[p][0], (lim-1)/2, (lim-1)/2, z1-z0);
                }
                break;
            }
        }
        assert(cnt <= 18);

        printf("%d\n", ans);
    }

    for(int i=0; i<=n; i++){
        if(tree[i][0]) delete tree[i][0];
        if(tree[i][1]) delete tree[i][1];
    }
}

Compilation message

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Runtime error 10 ms 10316 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Runtime error 10 ms 10316 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Runtime error 10 ms 10316 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 57140 KB Output is correct
2 Correct 142 ms 55836 KB Output is correct
3 Correct 124 ms 71720 KB Output is correct
4 Correct 128 ms 53968 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Runtime error 10 ms 10316 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -