oj.uz

답안 #986265

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
986265 2024-05-20T07:32:00 Z LOLOLO Magic Tree (CEOI19_magictree) C++17
11 / 100
 317 ms 104700 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e5 + 10;
int a[N], ans[N], sz[N], in[N], ou[N], timer = 0, used[N], b[N], laz[N * 4], seg[N * 4], val[N], k;
vector <int> ed[N];
stack <int> action;

void rollback() {
    while (sz(action)) {
        int t = action.top();
        laz[t] = seg[t] = 0;
        action.pop();
    }
}

void dfs(int u) {
    sz[u] = 1;
    timer++;
    in[u] = timer;
    b[timer] = a[u];
    for (auto x : ed[u]) {
        dfs(x);
        sz[u] += sz[x];
    }
    ou[u] = timer;
}

void push(int id) {
    int t = laz[id];
    laz[id * 2] += t;
    laz[id * 2 + 1] += t;
    seg[id * 2] += t;
    seg[id * 2 + 1] += t;
    action.push(id * 2);
    action.push(id * 2 + 1);
    laz[id] = 0;
}

void add(int id, int l, int r, int u, int v, int c) {
    if (l > v || r < u || u > v)
        return;

    if (l >= u && r <= v) {
        action.push(id);
        laz[id] += c;
        seg[id] += c;
        return;
    }

    action.push(id);
    push(id);
    int m = (l + r) / 2;
    add(id * 2, l, m, u, v, c);
    add(id * 2 + 1, m + 1, r, u, v, c);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}

void upd(int id, int l, int r, int p, int v) {
    if (l > p || r < p)
        return;

    if (l == r) {
        seg[id] = max(seg[id], v);
        return;
    }

    push(id);
    action.push(id);
    int m = (l + r) / 2;
    upd(id * 2, l, m, p, v);
    upd(id * 2 + 1, m + 1, r, p, v);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}

int get(int id, int l, int r, int u, int v) {
    if (l > v || r < u || u > v)
        return 0;

    if (l >= u && r <= v)
        return seg[id];

    action.push(id);
    push(id);
    int m = (l + r) / 2;
    return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
}

vector <pair <int, int>> save[N];

void dfs2(int u, bool is) {
    int mx = 0;
    for (auto x : ed[u]) {
        if (sz[x] > sz[mx])
            mx = x;
    }

    for (auto x : ed[u]) {
        if (x != mx) {
            dfs2(x, 0);
        }
    }

    if (mx)
        dfs2(mx, 1);


    for (auto x : ed[u]) {
        if (x != mx) {
            vector < vector <int>> seg;
            vector <pair <int, int>> point;
            int lst = 1, mx = 0;
            for (auto t : save[x]) {
                seg.pb({lst, t.f, mx});
                point.pb({t.f, get(1, 1, k, 1, t.f) + t.s});
                lst = t.f;
                mx = max(mx, t.s);
            }

            seg.pb({lst, k, mx});

            for (auto x : seg) {
                add(1, 1, k, x[0], x[1], x[2]);
            }

            for (auto x : point) {
                upd(1, 1, k, x.f, x.s);
            }
        }
    }

    int all = get(1, 1, k, 1, a[u]) + val[u];
    int v = get(1, 1, k, a[u], a[u]);
    if (all > v) {
        add(1, 1, k, a[u], a[u], all - v);
    }

    if (u == 1)
        ans[u] = get(1, 1, k, 1, k);

    if (is == 0) {
        for (int i = in[u]; i <= ou[u]; i++) {
            if (used[b[i]])
                continue;

            int cnt = get(1, 1, k, b[i], b[i]);
            save[u].pb({b[i], cnt});
            used[b[i]] = 1;
        }

        for (int i = in[u]; i <= ou[u]; i++) {
            used[b[i]] = 0;
        }
        rollback();
        sort(all(save[u]));
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m >> k;

    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        ed[x].pb(i);
    }

    for (int i = 0; i < m; i++) {
        int v, d, w;
        cin >> v >> d >> w;
        a[v] = d;
        val[v] = w;
    }

    dfs(1);
    dfs2(1, 1);

    cout << ans[1] << '\n';

    return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Incorrect 3 ms 14940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

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

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 15452 KB Output is correct
2 Correct 4 ms 15452 KB Output is correct
3 Correct 3 ms 15452 KB Output is correct
4 Correct 158 ms 104636 KB Output is correct
5 Correct 150 ms 104700 KB Output is correct
6 Correct 168 ms 104696 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Incorrect 3 ms 14940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Incorrect 3 ms 14940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Incorrect 3 ms 14940 KB Output isn't correct
3 Halted 0 ms 0 KB -