oj.uz

Submission #427921

# Submission time Handle Problem Language Result Execution time Memory
427921 2021-06-15T05:10:13 Z 반딧불(#7617) Counterspells (CPSPC17_counterspells) C++17
60 / 100
 1000 ms 87200 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    vector<int> minTree, maxTree, lazy;

    segTree(int n){
        minTree.resize(4*n);
        maxTree.resize(4*n);
        lazy.resize(4*n);
    }
    ~segTree(){}

    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:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 5 ms 5188 KB Output is correct
7 Correct 12 ms 5196 KB Output is correct
8 Correct 15 ms 8016 KB Output is correct
9 Correct 21 ms 7116 KB Output is correct
10 Correct 11 ms 7628 KB Output is correct
11 Correct 13 ms 9676 KB Output is correct
12 Correct 11 ms 7896 KB Output is correct
13 Correct 72 ms 6416 KB Output is correct
14 Correct 522 ms 6992 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 5 ms 5188 KB Output is correct
7 Correct 12 ms 5196 KB Output is correct
8 Correct 15 ms 8016 KB Output is correct
9 Correct 21 ms 7116 KB Output is correct
10 Correct 11 ms 7628 KB Output is correct
11 Correct 13 ms 9676 KB Output is correct
12 Correct 11 ms 7896 KB Output is correct
13 Correct 72 ms 6416 KB Output is correct
14 Correct 522 ms 6992 KB Output is correct
15 Correct 135 ms 34508 KB Output is correct
16 Correct 274 ms 27316 KB Output is correct
17 Correct 95 ms 32188 KB Output is correct
18 Correct 101 ms 54880 KB Output is correct
19 Correct 93 ms 34324 KB Output is correct
20 Execution timed out 1090 ms 17712 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 66552 KB Output is correct
2 Correct 199 ms 65128 KB Output is correct
3 Correct 146 ms 87200 KB Output is correct
4 Correct 143 ms 63280 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 4 ms 5324 KB Output is correct
6 Correct 5 ms 5188 KB Output is correct
7 Correct 12 ms 5196 KB Output is correct
8 Correct 15 ms 8016 KB Output is correct
9 Correct 21 ms 7116 KB Output is correct
10 Correct 11 ms 7628 KB Output is correct
11 Correct 13 ms 9676 KB Output is correct
12 Correct 11 ms 7896 KB Output is correct
13 Correct 72 ms 6416 KB Output is correct
14 Correct 522 ms 6992 KB Output is correct
15 Correct 135 ms 34508 KB Output is correct
16 Correct 274 ms 27316 KB Output is correct
17 Correct 95 ms 32188 KB Output is correct
18 Correct 101 ms 54880 KB Output is correct
19 Correct 93 ms 34324 KB Output is correct
20 Execution timed out 1090 ms 17712 KB Time limit exceeded
21 Halted 0 ms 0 KB -