oj.uz

Submission #956650

# Submission time Handle Problem Language Result Execution time Memory
956650 2024-04-02T09:42:01 Z thangdz2k7 Magic Tree (CEOI19_magictree) C++17
34 / 100
 723 ms 1048576 KB 
// author : HuuHung
// 25.3.2024


#include <bits/stdc++.h>
#define int long long
#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);
}


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(long long int, long long int)':
magictree.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         int mid = l + r >> 1;
      |                   ~~^~~
magictree.cpp: In member function 'Node* persis::update(Node*, long long int, long long int, long long int, long long int, long long int)':
magictree.cpp:102:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |         int mid = l + r >> 1;
      |                   ~~^~~
magictree.cpp: In member function 'long long int persis::get(Node*, long long int, long long int, long long int)':
magictree.cpp:114:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         int mid = l + r >> 1;
      |                   ~~^~~
magictree.cpp: In member function 'long long int persis::walk(Node*, long long int, long long int, long long int)':
magictree.cpp:126:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |         int mid = l + r >> 1;
      |                   ~~^~~
magictree.cpp: In member function 'Node* persis::assign(Node*, long long int, long long int, long long int, long long int, long long int)':
magictree.cpp:136:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  136 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 723 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 91 ms 113552 KB Output is correct
2 Correct 94 ms 113748 KB Output is correct
3 Correct 74 ms 113748 KB Output is correct
4 Runtime error 706 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 122 ms 57680 KB Output is correct
2 Correct 97 ms 38880 KB Output is correct
3 Correct 86 ms 59968 KB Output is correct
4 Correct 68 ms 59596 KB Output is correct
5 Correct 67 ms 71344 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 19036 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19132 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 5 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct
10 Correct 319 ms 292268 KB Output is correct
11 Correct 220 ms 172748 KB Output is correct
12 Correct 214 ms 249168 KB Output is correct
13 Correct 254 ms 269776 KB Output is correct
14 Correct 196 ms 255508 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 711 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 6 ms 19036 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19132 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 5 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct
10 Correct 91 ms 113552 KB Output is correct
11 Correct 94 ms 113748 KB Output is correct
12 Correct 74 ms 113748 KB Output is correct
13 Runtime error 706 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 6 ms 19036 KB Output is correct
2 Correct 5 ms 19036 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19132 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 5 ms 19036 KB Output is correct
9 Correct 4 ms 19032 KB Output is correct
10 Runtime error 723 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -