oj.uz

Submission #956663

# Submission time Handle Problem Language Result Execution time Memory
956663 2024-04-02T09:51:04 Z thangdz2k7 Magic Tree (CEOI19_magictree) C++17
34 / 100
 925 ms 1048576 KB 
// 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;
}

Compilation message

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 925 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 111444 KB Output is correct
2 Correct 81 ms 111696 KB Output is correct
3 Correct 72 ms 111700 KB Output is correct
4 Runtime error 695 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 48928 KB Output is correct
2 Correct 81 ms 30808 KB Output is correct
3 Correct 70 ms 54416 KB Output is correct
4 Correct 60 ms 49364 KB Output is correct
5 Correct 69 ms 67520 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 288 ms 280516 KB Output is correct
11 Correct 194 ms 161872 KB Output is correct
12 Correct 221 ms 243448 KB Output is correct
13 Correct 212 ms 259172 KB Output is correct
14 Correct 192 ms 251356 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 693 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 77 ms 111444 KB Output is correct
11 Correct 81 ms 111696 KB Output is correct
12 Correct 72 ms 111700 KB Output is correct
13 Runtime error 695 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 4 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Runtime error 925 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -