oj.uz

Submission #429394

# Submission time Handle Problem Language Result Execution time Memory
429394 2021-06-15T22:31:15 Z 최서현(#7487) Counterspells (CPSPC17_counterspells) C++17
100 / 100
 765 ms 44960 KB 
#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> gph[202020];
int par[202020];
int in[202020];
int rev[202020];
int sz[202020];
int dep[202020];
int up[202020];
int icnt = 0;

void dfs2(int x)
{
    sz[x] = 1;
    for(int i = 0; i < (int)gph[x].size(); ++i)
    {
        dfs2(gph[x][i]);
        sz[x] += sz[gph[x][i]];
        if(sz[gph[x][0]] < sz[gph[x][i]]) swap(gph[x][0], gph[x][i]);
    }
}

void dfs3(int x, int d, int u)
{
    dep[x] = d;
    up[x] = u;
    in[x] = icnt++;
    for(int i = 0; i < (int)gph[x].size(); ++i)
        dfs3(gph[x][i], d + 1, i ? gph[x][i] : u);
}

const int INF = (int)1e9 + 7;
struct Node
{
    int mx[2], mn[2], lazy[2];
    Node(void) { mx[0] = mx[1] = -INF; mn[0] = mn[1] = INF; lazy[0] = lazy[1] = 0; }
}seg[808080];

void prop(int ind)
{
    for(auto x : {ind << 1, ind << 1 | 1})
    {
        seg[x].lazy[0] += seg[ind].lazy[0];
        seg[x].lazy[1] += seg[ind].lazy[1];
        seg[x].mx[0] += seg[ind].lazy[0];
        seg[x].mx[1] += seg[ind].lazy[1];
        seg[x].mn[0] += seg[ind].lazy[0];
        seg[x].mn[1] += seg[ind].lazy[1];
    }
    seg[ind].lazy[0] = seg[ind].lazy[1] = 0;
}
void mrge(int ind)
{
    Node &nd = seg[ind], &x = seg[ind << 1], &y = seg[ind << 1 | 1];
    nd.mx[0] = max(x.mx[0], y.mx[0]);
    nd.mx[1] = max(x.mx[1], y.mx[1]);
    nd.mn[0] = min(x.mn[0], y.mn[0]);
    nd.mn[1] = min(x.mn[1], y.mn[1]);
}
void upd(int ind, int s, int e, int l, int r, int x)
{
    if(e <= l || r <= s) return;
    if(l <= s && e <= r)
    {
        seg[ind].mx[0] += x;
        seg[ind].mx[1] -= x;
        seg[ind].mn[0] += x;
        seg[ind].mn[1] -= x;
        seg[ind].lazy[0] += x;
        seg[ind].lazy[1] -= x;
        return;
    }

    prop(ind);
    int mid = s + e >> 1;
    upd(ind << 1, s, mid, l, r, x);
    upd(ind << 1 | 1, mid, e, l, r, x);
    mrge(ind);
}
void updp(int ind, int s, int e, int pos, bool f)
{
    if(s + 1 == e)
    {
        if(f) seg[ind].mn[0] = seg[ind].mx[0] = 0;
        else seg[ind].mn[1] = seg[ind].mx[1] = 0;
        return;
    }

    prop(ind);
    int mid = s + e >> 1;
    if(pos < mid) updp(ind << 1, s, mid, pos, f);
    else updp(ind << 1 | 1, mid, e, pos, f);
    mrge(ind);
}
int lb(int ind, int s, int e, int l, int r, int ev, int od)
{
    if(e <= l || r <= s) return -1;
    if(l <= s && e <= r && seg[ind].mn[0] >= ev && seg[ind].mn[1] >= od && seg[ind].mx[0] <= ev && seg[ind].mx[1] <= od) return -1;
    if(s + 1 == e) return s;

    prop(ind);
    int mid = s + e >> 1;
    int t = lb(ind << 1 | 1, mid, e, l, r, ev, od);
    if(t != -1) return t;
    return lb(ind << 1, s, mid, l, r, ev, od);
}

int qry(int x, int k)
{
    int t = lb(1, 0, N, in[up[x]], in[x] + 1, (in[x] & 1 ? 1 - k : k), (in[x] & 1 ? k : 1 - k));
    int ret = in[x] - (t == -1 ? in[up[x]] - 1 : t);
    upd(1, 0, N, (t == -1 ? in[up[x]] : t), in[x] + 1, (in[x] & 1 ? 2 * k - 1 : 1 - 2 * k));
    if(t != -1 || up[x] == 0) return ret;
    return ret + qry(par[up[x]], ((in[x] - in[up[x]]) & 1) ? k : 1 - k);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen("input.txt", "r", stdin);

    int n; cin >> n;
    N = n + 1;
    for(int i = 1; i <= n; ++i)
    {
        int x; cin >> x;
        par[i] = x;
        gph[x].push_back(i);
    }

    dfs2(0);
    dfs3(0, 0, 0);
    for(int i = 0; i <= n; ++i) rev[in[i]] = i;

    for(int i = 1; i <= n; ++i)
    {
        updp(1, 0, N, in[i - 1], ~in[i - 1] & 1);
        cout << qry(par[i], 0) << '\n';
    }
}

Compilation message

Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:79:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int mid = s + e >> 1;
      |               ~~^~~
Main.cpp: In function 'void updp(int, int, int, int, bool)':
Main.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     int mid = s + e >> 1;
      |               ~~^~~
Main.cpp: In function 'int lb(int, int, int, int, int, int, int)':
Main.cpp:106:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int mid = s + e >> 1;
      |               ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24012 KB Output is correct
2 Correct 17 ms 24124 KB Output is correct
3 Correct 18 ms 24072 KB Output is correct
4 Correct 18 ms 24052 KB Output is correct
5 Correct 17 ms 23988 KB Output is correct
6 Correct 18 ms 24124 KB Output is correct
7 Correct 17 ms 24012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24012 KB Output is correct
2 Correct 17 ms 24124 KB Output is correct
3 Correct 18 ms 24072 KB Output is correct
4 Correct 18 ms 24052 KB Output is correct
5 Correct 17 ms 23988 KB Output is correct
6 Correct 18 ms 24124 KB Output is correct
7 Correct 17 ms 24012 KB Output is correct
8 Correct 33 ms 24340 KB Output is correct
9 Correct 32 ms 25060 KB Output is correct
10 Correct 31 ms 24408 KB Output is correct
11 Correct 28 ms 24400 KB Output is correct
12 Correct 32 ms 24396 KB Output is correct
13 Correct 39 ms 24556 KB Output is correct
14 Correct 36 ms 24468 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24012 KB Output is correct
2 Correct 17 ms 24124 KB Output is correct
3 Correct 18 ms 24072 KB Output is correct
4 Correct 18 ms 24052 KB Output is correct
5 Correct 17 ms 23988 KB Output is correct
6 Correct 18 ms 24124 KB Output is correct
7 Correct 17 ms 24012 KB Output is correct
8 Correct 33 ms 24340 KB Output is correct
9 Correct 32 ms 25060 KB Output is correct
10 Correct 31 ms 24408 KB Output is correct
11 Correct 28 ms 24400 KB Output is correct
12 Correct 32 ms 24396 KB Output is correct
13 Correct 39 ms 24556 KB Output is correct
14 Correct 36 ms 24468 KB Output is correct
15 Correct 265 ms 27972 KB Output is correct
16 Correct 235 ms 34124 KB Output is correct
17 Correct 196 ms 27584 KB Output is correct
18 Correct 156 ms 27120 KB Output is correct
19 Correct 205 ms 28360 KB Output is correct
20 Correct 315 ms 29608 KB Output is correct
21 Correct 216 ms 29980 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 32336 KB Output is correct
2 Correct 450 ms 32040 KB Output is correct
3 Correct 262 ms 29012 KB Output is correct
4 Correct 410 ms 32532 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24012 KB Output is correct
2 Correct 17 ms 24124 KB Output is correct
3 Correct 18 ms 24072 KB Output is correct
4 Correct 18 ms 24052 KB Output is correct
5 Correct 17 ms 23988 KB Output is correct
6 Correct 18 ms 24124 KB Output is correct
7 Correct 17 ms 24012 KB Output is correct
8 Correct 33 ms 24340 KB Output is correct
9 Correct 32 ms 25060 KB Output is correct
10 Correct 31 ms 24408 KB Output is correct
11 Correct 28 ms 24400 KB Output is correct
12 Correct 32 ms 24396 KB Output is correct
13 Correct 39 ms 24556 KB Output is correct
14 Correct 36 ms 24468 KB Output is correct
15 Correct 265 ms 27972 KB Output is correct
16 Correct 235 ms 34124 KB Output is correct
17 Correct 196 ms 27584 KB Output is correct
18 Correct 156 ms 27120 KB Output is correct
19 Correct 205 ms 28360 KB Output is correct
20 Correct 315 ms 29608 KB Output is correct
21 Correct 216 ms 29980 KB Output is correct
22 Correct 765 ms 32336 KB Output is correct
23 Correct 450 ms 32040 KB Output is correct
24 Correct 262 ms 29012 KB Output is correct
25 Correct 410 ms 32532 KB Output is correct
26 Correct 683 ms 32356 KB Output is correct
27 Correct 447 ms 44960 KB Output is correct
28 Correct 463 ms 32220 KB Output is correct
29 Correct 315 ms 29956 KB Output is correct
30 Correct 448 ms 32632 KB Output is correct
31 Correct 717 ms 35700 KB Output is correct
32 Correct 492 ms 36972 KB Output is correct