제출 #956663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956663		thangdz2k7	Magic Tree (CEOI19_magictree)	C++17	34 / 100	925 ms	1048576 KiB

magictree

// author : HuuHung
// 25.3.2024


#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second
#define ll long long
#define lb long double
#define pb push_back
#define vi vector <int>
#define vll vector <ll>
#define Bit(x, i) ((x) >> (i) & 1)
#define Mask(i) (1ll << (i))
#define All(v) (v).begin(), (v).end()

using namespace std;

void maxzi(int &a, int b){
    a = max(a, b);
}

void minzi(int &a, int b){
    a = min(a, b);
}

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int LG = 20;

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int Pow(int a, int b){
    if (b == 0) return 1;
    if (b % 2) return 1ll * a * Pow(a, b - 1) % mod;
    int c = Pow(a, b / 2);
    return 1ll * c * c % mod;
}

// * end

struct Node {
    Node *left, *right;
    ll Max, lz;
    Node (ll val){
        left = nullptr;
        right = nullptr;
        Max = val;
        lz = 0;
    }

    Node (Node *old, ll val){
        this -> left = old -> left;
        this -> right = old -> right;
        this -> Max = old -> Max;
        this -> lz = old -> lz;
        this -> Max += val;
        this -> lz += val;
    }

    Node (Node *left, Node *right){
        this -> left = left;
        this -> right = right;
        this -> Max = max(left -> Max, right -> Max);
        this -> lz = 0;
    }
};

struct persis{
    Node *ver[N];

    Node *build(int l, int r){
        if (l == r) return new Node(0ll);
        int mid = l + r >> 1;
        return new Node(build(l, mid), build(mid + 1, r));
    }

    void dw(Node *cur){
        if (cur -> left == nullptr){
            //return cur -> Max;
            cur -> left = new Node(cur -> Max - cur -> lz);
            cur -> right = new Node(cur -> Max - cur -> lz);
        }
        cur -> left -> Max += cur -> lz;
        cur -> right -> Max += cur -> lz;
        cur -> left -> lz += cur -> lz;
        cur -> right -> lz += cur -> lz;
        cur -> lz = 0;
    }

    Node *update(Node *old, int l, int r, int u, int v, ll val){
        if (u <= l && r <= v){
            return new Node(old, val);
        }

        int mid = l + r >> 1;
        dw(old);
        if (mid < u) return new Node(old -> left, update(old -> right, mid + 1, r, u, v, val));
        if (mid + 1 > v) return new Node(update(old -> left, l, mid, u, v, val), old -> right);
        return new Node(update(old -> left, l, mid, u, v, val), update(old -> right, mid + 1, r, u, v, val));
    }

    ll get(Node *cur, int l, int r, int u){
        if (l > u) return 0ll;
        if (r <= u) return cur -> Max;

        dw(cur);
        int mid = l + r >> 1;
        return max(get(cur -> left, l, mid, u), get(cur -> right, mid + 1, r, u));
    }

    int walk(Node *cur, int l, int r, ll val){
        if (cur -> left == nullptr || l == r) {
            if (cur -> Max > val) return l - 1;
            else return r;
        }

        dw(cur);

        int mid = l + r >> 1;
        if (cur -> left -> Max < val) return walk(cur -> right, mid + 1, r, val);
        return walk(cur -> left, l, mid, val);
    }

    Node *assign(Node *old, int l, int r, int u, int v, ll val){
        if (u <= l && r <= v){
            return new Node(val);
        }

        int mid = l + r >> 1;
        dw(old);
        if (mid < u) return new Node(old -> left, assign(old -> right, mid + 1, r, u, v, val));
        if (mid + 1 > v) return new Node(assign(old -> left, l, mid, u, v, val), old -> right);
        return new Node(assign(old -> left, l, mid, u, v, val), assign(old -> right, mid + 1, r, u, v, val));
    }
} ac;

int n, m, k;
vector <int> adj[N];
int d[N], w[N];
set <int> event[N];

void dfs(int u){
    ac.ver[u] = ac.build(1, k);
    for (int v : adj[u]){
        dfs(v);
        if (event[u].size() < event[v].size()){
            swap(event[u], event[v]);
            swap(ac.ver[u], ac.ver[v]);
        }
        int last = 0;
        for (auto x : event[v]){
            event[u].insert(x);
            if (!last){
                last = x;
                continue;
            }
            ac.ver[u] = ac.update(ac.ver[u], 1, k, last, x - 1, ac.get(ac.ver[v], 1, k, last));
            last = x;
        }
        event[v].clear();
    }

    //if (u == 6) cout << ac.get(ac.ver[u], 1, k, 8) << endl;
    if (d[u]){
        //cout << u << ' ' << d[u] << endl;
        event[u].insert(d[u]);
        ll val = ac.get(ac.ver[u], 1, k, d[u]) + w[u];
        int pos = ac.walk(ac.ver[u], 1, k, val);
        //if (u == 6) cout << val << ' ' << d[u] << ' ' << pos << '\n';
        //if (u == 2) ac.ver[u] = ac.assign(ac.ver[u], 1, k, 1, 10, val);
        ac.ver[u] = ac.assign(ac.ver[u], 1, k, d[u], pos, val);
        //if (u == 2) cout << ac.get(ac.ver[u], 1, k, 9) << endl;
    }
}

void solve(){
    cin >> n >> m >> k;
    for (int i = 2; i <= n; ++ i){
        int p; cin >> p;
        adj[p].pb(i);
    }

    for (int i = 1; i <= m; ++ i){
        int v; cin >> v;
        cin >> d[v] >> w[v];
    }

    for (int i = 1; i <= n; ++ i) event[i].insert(k + 1);
    dfs(1);

    cout << ac.get(ac.ver[1], 1, k, k);
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t --) solve();

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

magictree.cpp: In member function 'Node* persis::build(int, int)':
magictree.cpp:79:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |         int mid = l + r >> 1;
      |                   ~~^~~
magictree.cpp: In member function 'Node* persis::update(Node*, int, int, int, int, long long int)':
magictree.cpp:101:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |         int mid = l + r >> 1;
      |                   ~~^~~
magictree.cpp: In member function 'long long int persis::get(Node*, int, int, int)':
magictree.cpp:113:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |         int mid = l + r >> 1;
      |                   ~~^~~
magictree.cpp: In member function 'int persis::walk(Node*, int, int, long long int)':
magictree.cpp:125:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |         int mid = l + r >> 1;
      |                   ~~^~~
magictree.cpp: In member function 'Node* persis::assign(Node*, int, int, int, int, long long int)':
magictree.cpp:135:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |         int mid = l + r >> 1;
      |                   ~~^~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17