oj.uz

답안 #429215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429215 2021-06-15T19:03:52 Z 최서현(#7487) Counterspells (CPSPC17_counterspells) C++17
0 / 100
 945 ms 32316 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, 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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 24072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 24072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 24072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 945 ms 32316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 24072 KB Output isn't correct
2 Halted 0 ms 0 KB -