oj.uz

Submission #427922

# Submission time Handle Problem Language Result Execution time Memory
427922 2021-06-15T05:13:57 Z 반딧불(#7617) Counterspells (CPSPC17_counterspells) C++17
60 / 100
 1000 ms 71664 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;

        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: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 4 ms 5116 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 9 ms 5256 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 4 ms 5116 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 9 ms 5256 KB Output is correct
8 Correct 12 ms 7500 KB Output is correct
9 Correct 19 ms 7336 KB Output is correct
10 Correct 9 ms 7244 KB Output is correct
11 Correct 12 ms 8780 KB Output is correct
12 Correct 10 ms 7420 KB Output is correct
13 Correct 46 ms 6348 KB Output is correct
14 Correct 341 ms 6816 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 4 ms 5116 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 9 ms 5256 KB Output is correct
8 Correct 12 ms 7500 KB Output is correct
9 Correct 19 ms 7336 KB Output is correct
10 Correct 9 ms 7244 KB Output is correct
11 Correct 12 ms 8780 KB Output is correct
12 Correct 10 ms 7420 KB Output is correct
13 Correct 46 ms 6348 KB Output is correct
14 Correct 341 ms 6816 KB Output is correct
15 Correct 111 ms 30036 KB Output is correct
16 Correct 239 ms 28296 KB Output is correct
17 Correct 68 ms 27960 KB Output is correct
18 Correct 78 ms 45480 KB Output is correct
19 Correct 69 ms 29620 KB Output is correct
20 Execution timed out 1085 ms 17692 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 57132 KB Output is correct
2 Correct 142 ms 55936 KB Output is correct
3 Correct 123 ms 71664 KB Output is correct
4 Correct 130 ms 53896 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 5116 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 9 ms 5256 KB Output is correct
8 Correct 12 ms 7500 KB Output is correct
9 Correct 19 ms 7336 KB Output is correct
10 Correct 9 ms 7244 KB Output is correct
11 Correct 12 ms 8780 KB Output is correct
12 Correct 10 ms 7420 KB Output is correct
13 Correct 46 ms 6348 KB Output is correct
14 Correct 341 ms 6816 KB Output is correct
15 Correct 111 ms 30036 KB Output is correct
16 Correct 239 ms 28296 KB Output is correct
17 Correct 68 ms 27960 KB Output is correct
18 Correct 78 ms 45480 KB Output is correct
19 Correct 69 ms 29620 KB Output is correct
20 Execution timed out 1085 ms 17692 KB Time limit exceeded
21 Halted 0 ms 0 KB -