oj.uz

Submission #956646

# Submission time Handle Problem Language Result Execution time Memory
956646 2024-04-02T09:38:43 Z thangdz2k7 Magic Tree (CEOI19_magictree) C++17
34 / 100
 1010 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;
        }
    }

    //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);
}


int 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 5 ms 16984 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 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 1010 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 69 ms 111344 KB Output is correct
2 Correct 71 ms 111596 KB Output is correct
3 Correct 76 ms 111516 KB Output is correct
4 Runtime error 752 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 123 ms 57324 KB Output is correct
2 Correct 77 ms 38596 KB Output is correct
3 Correct 78 ms 60752 KB Output is correct
4 Correct 69 ms 59080 KB Output is correct
5 Correct 71 ms 72992 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16984 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 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 342 ms 291472 KB Output is correct
11 Correct 215 ms 171856 KB Output is correct
12 Correct 229 ms 249464 KB Output is correct
13 Correct 265 ms 268496 KB Output is correct
14 Correct 201 ms 256560 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 745 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 5 ms 16984 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 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 69 ms 111344 KB Output is correct
11 Correct 71 ms 111596 KB Output is correct
12 Correct 76 ms 111516 KB Output is correct
13 Runtime error 752 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 5 ms 16984 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 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 1010 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -