oj.uz

Submission #427924

# Submission time Handle Problem Language Result Execution time Memory
427924 2021-06-15T05:17:01 Z 반딧불(#7617) Counterspells (CPSPC17_counterspells) C++17
100 / 100
 517 ms 85932 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[x] += sz[y];
        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){
            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;
            }
        }

        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:135:13: warning: unused variable 'cnt' [-Wunused-variable]
  135 |         int cnt = 0;
      |             ^~~
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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 5 ms 5244 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 6 ms 5196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 5 ms 5244 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 6 ms 5196 KB Output is correct
8 Correct 31 ms 7500 KB Output is correct
9 Correct 18 ms 7336 KB Output is correct
10 Correct 10 ms 7244 KB Output is correct
11 Correct 12 ms 8804 KB Output is correct
12 Correct 10 ms 7412 KB Output is correct
13 Correct 18 ms 6448 KB Output is correct
14 Correct 14 ms 6684 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 5 ms 5244 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 6 ms 5196 KB Output is correct
8 Correct 31 ms 7500 KB Output is correct
9 Correct 18 ms 7336 KB Output is correct
10 Correct 10 ms 7244 KB Output is correct
11 Correct 12 ms 8804 KB Output is correct
12 Correct 10 ms 7412 KB Output is correct
13 Correct 18 ms 6448 KB Output is correct
14 Correct 14 ms 6684 KB Output is correct
15 Correct 159 ms 30104 KB Output is correct
16 Correct 252 ms 28456 KB Output is correct
17 Correct 77 ms 28004 KB Output is correct
18 Correct 78 ms 45452 KB Output is correct
19 Correct 66 ms 29660 KB Output is correct
20 Correct 161 ms 17768 KB Output is correct
21 Correct 198 ms 26516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 57332 KB Output is correct
2 Correct 143 ms 55932 KB Output is correct
3 Correct 122 ms 71672 KB Output is correct
4 Correct 129 ms 53956 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 5 ms 5244 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 6 ms 5196 KB Output is correct
8 Correct 31 ms 7500 KB Output is correct
9 Correct 18 ms 7336 KB Output is correct
10 Correct 10 ms 7244 KB Output is correct
11 Correct 12 ms 8804 KB Output is correct
12 Correct 10 ms 7412 KB Output is correct
13 Correct 18 ms 6448 KB Output is correct
14 Correct 14 ms 6684 KB Output is correct
15 Correct 159 ms 30104 KB Output is correct
16 Correct 252 ms 28456 KB Output is correct
17 Correct 77 ms 28004 KB Output is correct
18 Correct 78 ms 45452 KB Output is correct
19 Correct 66 ms 29660 KB Output is correct
20 Correct 161 ms 17768 KB Output is correct
21 Correct 198 ms 26516 KB Output is correct
22 Correct 320 ms 57332 KB Output is correct
23 Correct 143 ms 55932 KB Output is correct
24 Correct 122 ms 71672 KB Output is correct
25 Correct 129 ms 53956 KB Output is correct
26 Correct 300 ms 57360 KB Output is correct
27 Correct 517 ms 51724 KB Output is correct
28 Correct 170 ms 56952 KB Output is correct
29 Correct 152 ms 85932 KB Output is correct
30 Correct 159 ms 54208 KB Output is correct
31 Correct 344 ms 30344 KB Output is correct
32 Correct 474 ms 52592 KB Output is correct