oj.uz

Submission #771876

# Submission time Handle Problem Language Result Execution time Memory
771876 2023-07-03T11:05:10 Z JakobZorz Magic Tree (CEOI19_magictree) C++17
100 / 100
 566 ms 161900 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <map>
#include <cstring>
#include <sstream>
 
#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD = 1e9+7;
typedef pair<ld,ld> point;
//#define x first
//#define y second

//#define SEGTREE
//#define TREE
//#define DSU
//#define MATH
 
#ifdef SEGTREE
template<class Type>
class SegmentTree {
    Type (*func)(Type a, Type b);
    vector<Type> nodes;
    vector<int> l;
    vector<int> r;
    int size_log2;
    Type neutral;
    
    void init_node(int node) {
        if(node >= (1 << size_log2))
            return;
        
        l[2 * node] = l[node];
        r[2 * node] = (l[node] + r[node]) / 2;
        init_node(2 * node);
        
        l[2 * node + 1] = (l[node] + r[node]) / 2;
        r[2 * node + 1] = r[node];
        init_node(2 * node + 1);
        
        nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
    }
    
    void update_node(int node) {
        if(node < (1 << size_log2))
            nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
        
        if(node != 1)
            update_node(node / 2);
    }
    
    Type get(int node, int ll_, int rr) {
        if(rr <= l[node] || ll_ >= r[node])
            return neutral;
        
        if(ll_ <= l[node] && rr >= r[node])
            return nodes[node];
        
        Type left = get(2 * node, ll_, rr);
        Type right = get(2 * node + 1, ll_, rr);
        
        return func(left, right);
    }
    
public:
    SegmentTree(Type (*func)(Type a, Type b), vector<Type> vector, Type neutral) : func(func), neutral(neutral) {
        size_log2 = 0;
        while((1 << size_log2) < vector.size())
            size_log2++;
        
        nodes.resize((1 << size_log2) * 2);
        l.resize((1 << size_log2) * 2);
        r.resize((1 << size_log2) * 2);
        
        for(int i = 0; i < vector.size(); i++)
            nodes[(1 << size_log2) + i] = vector[i];
        
        l[1] = 0;
        r[1] = 1 << size_log2;
        init_node(1);
    }
    
    void set(int idx, Type el) {
        nodes[(1 << size_log2) + idx] = el;
        update_node((1 << size_log2) + idx);
    }
    
    Type get(int l, int r) {
        return get(1, l, r);
    }
    
    Type get(int idx) {
        return nodes[(1 << size_log2) + idx];
    }
    
    Type get() {
        return nodes[1];
    }
    
    int get_first_larger_or_eq_than(int bound) {
        return get_first_larger_or_eq_than(1, bound);
    }
    
    int get_first_larger_or_eq_than(int node, int bound) {
        if(node >= (1 << size_log2)) {
            return node - (1 << size_log2);
        }
        
        if(nodes[node * 2] > bound)
            return get_first_larger_or_eq_than(node * 2, bound);
        else
            return get_first_larger_or_eq_than(node * 2 + 1, bound - nodes[node * 2]);
    }
};
 
#endif
 
#ifdef TREE
#define POW 18
 
struct Node {
    int parents[POW];
    vector<int> conns;
    int depth;
    int value;
    int subtree_depth;
    int subtree_size;
    int euler;
    int val;
    int res;
};
 
ll add(ll a, ll b) {
    return a + b;
}
 
Node nodes[200000];
int n;
 
int setup(int node, int depth, int euler, ll dist) {
    dist += nodes[node].value;
    nodes[node].depth = depth;
    nodes[node].euler = euler++;
    
    
    for(int i = 1; i < POW; i++) {
        nodes[node].parents[i] = nodes[nodes[node].parents[i - 1]].parents[i - 1];
    }
    
    int size = 1;
    
    for(int i = 0; i < nodes[node].conns.size(); i++) {
        int child = nodes[node].conns[i];
        if(child != nodes[node].parents[0]) {
            nodes[child].parents[0] = node;
            euler = setup(child, depth + 1, euler, dist);
            size += nodes[child].subtree_size;
        }
    }
    nodes[node].subtree_size = size;
    return euler;
}
 
void setup_tree(int root) {
    nodes[root].parents[0] = root;
    setup(root, 0, 0, 0);
}
 
int get_subtree_depth(int node) {
    if(nodes[node].subtree_depth)
        return nodes[node].subtree_depth;
    
    int max_depth = 1;
    for(int child : nodes[node].conns) {
        if(child == nodes[node].parents[0])
            continue;
        max_depth = max(max_depth, get_subtree_depth(child) + 1);
    }
    nodes[node].subtree_depth = max_depth;
    return max_depth;
}
 
int get_parent(int node, int depth) {
    if(depth > nodes[node].depth)
        return -1;
    
    int climber = node;
    for(int i = 0; i < POW; i++) {
        if(depth & (1 << i) && climber != -1)
            climber = nodes[climber].parents[i];
    }
    
    return climber;
}

bool is_sub(int a,int b){
    return get_parent(a,nodes[a].depth-nodes[b].depth)==b;
}
 
int lca(int a, int b) {
    if(nodes[a].depth < nodes[b].depth)
        swap(a, b);
    
    a = get_parent(a, nodes[a].depth - nodes[b].depth);
    
    if(a == b)
        return a;
    
    for(int i = POW - 1; i >= 0; i--) {
        if(nodes[a].parents[i] != nodes[b].parents[i]) {
            a = nodes[a].parents[i];
            b = nodes[b].parents[i];
        }
    }
    
    return nodes[a].parents[0];
}
 
#endif
 
#ifdef DSU
 
class Dsu {
    vector<int> arr;
    int num_sets;
    
public:
    Dsu(int size) {
        arr = vector<int>(size, -1);
        num_sets = size;
    }
    
    int merge(int a, int b) {
        a = get(a);
        b = get(b);
        
        if(a == b)
            return a;
        
        if(arr[a] > arr[b])
            swap(a, b);
        
        arr[a] += arr[b];
        arr[b] = a;
        num_sets--;
        return a;
    }
    
    int get(int a) {
        if(arr[a] < 0)
            return a;
        arr[a] = get(arr[a]);
        return get(arr[a]);
    }
    
    int get_size(int a) {
        return -arr[get(a)];
    }
    
    int get_num_sets() {
        return num_sets;
    }
};
 
#endif
 
#ifdef MATH
 
ll dpf[2000001];
ll factorial(ll n) {
    if(n == 0)
        return 1;
    
    if(dpf[n])
        return dpf[n];
    
    ll result = factorial(n - 1) * n;
    result %= MOD;
    dpf[n] = result;
    return result;
}
 
ll powm(ll base, ll exp) {
    ll result = 1;
    
    for(int i = 0; i < 64; i++) {
        if((exp >> i) % 2 == 1) {
            result *= base;
            result %= MOD;
        }
        base *= base;
        base %= MOD;
    }
    
    return result;
}
 
ll inverse(ll n) {
    return powm(n, MOD - 2);
}
 
ll dpif[2000001];
ll inverse_factorial(ll n) {
    if(dpif[n])
        return dpif[n];
    
    ll result = inverse(factorial(n));
    dpif[n] = result;
    return result;
}
 
ll choose(ll n, ll k) {
    return (((factorial(n)*inverse_factorial(n-k))%MOD)*inverse_factorial(k))%MOD;
}
 
ll gcd(ll a, ll b){
    if(a==b)
        return a;
    if(a<b)
        swap(a,b);
    if(b==0)
        return a;
    return gcd(b, a%b);
}
 
#endif

int n,m,k;
vector<int>children[100001];
vector<int>children2[100001];
int fruit_day[100001];
int fruit_juice[100001];
int fruit_day2[100001];
int fruit_juice2[100001];
int curr_node=1;
int max_day;

struct IncreasingArray{
    vector<ll>tree;
    vector<int>c1,c2,l,r;
    int root=-1;
    
    int new_node(){
        int node=(int)tree.size();
        tree.push_back(0);
        c1.push_back(-1);
        c2.push_back(-1);
        l.push_back(0);
        r.push_back(0);
        return node;
    }
    
    void update_node(int node){
        tree[node]=0;
        if(c1[node]!=-1)
            tree[node]+=tree[c1[node]];
        if(c2[node]!=-1)
            tree[node]+=tree[c2[node]];
    }
    
    ll get_val(int node,int i){
        if(node==-1)
            return 0;
        if(r[node]<=i)
            return tree[node];
        if(l[node]>=i)
            return 0;
        return get_val(c1[node],i)+get_val(c2[node],i);
    }
    
    void add_val(int node,int i,ll val){
        if(l[node]==r[node]-1){
            tree[node]+=val;
            return;
        }
        
        int mid=(l[node]+r[node])/2;
        if(i>=mid){
            if(c2[node]==-1){
                c2[node]=new_node();
                l[c2[node]]=mid;
                r[c2[node]]=r[node];
            }
            add_val(c2[node],i,val);
        }else{
            if(c1[node]==-1){
                c1[node]=new_node();
                l[c1[node]]=l[node];
                r[c1[node]]=mid;
            }
            add_val(c1[node],i,val);
        }
        update_node(node);
    }
    
    ll remove(int node,int i,ll val){
        if(node==-1)
            return val;
        if(val==0)
            return 0;
        if(r[node]<=i)
            return val;
        if(l[node]==r[node]-1){
            ll diff=min(val,tree[node]);
            tree[node]-=diff;
            return val-diff;
        }
        val=remove(c1[node],i,val);
        if(val==0){
            update_node(node);
            return 0;
        }
        val=remove(c2[node],i,val);
        update_node(node);
        return val;
    }
    
    vector<pair<int,ll>> collection;
    void collect(int node){
        if(node==-1)
            return;
        if(l[node]==r[node]-1){
            if(tree[node]==0)
                return;
            collection.emplace_back(l[node],tree[node]);
            return;
        }
        collect(c1[node]);
        collect(c2[node]);
    }
    
public:
    IncreasingArray(){
        root=new_node();
        r[root]=1<<17;
    }
    
    void add_array(IncreasingArray&a){
        a.collect(a.root);
        for(auto i:a.collection)
            add_val(root,i.first,i.second);
    }
    
    void add_bound(int x,ll s){
        s-=get_val(root,x+1);
        add_val(root,x,s);
        remove(root,x+1,s);
    }
    
    ll get(int i){
        return get_val(root,i+1);
    }
    
    int size(){
        return (int)tree.size();
    }
    
    void swap_with(IncreasingArray&a){
        swap(tree,a.tree);
        swap(c1,a.c1);
        swap(c2,a.c2);
        swap(l,a.l);
        swap(r,a.r);
        swap(root,a.root);
    }
};

IncreasingArray dp[100001];

void init_node(int node,int parent){
    if(fruit_juice[node]){
        children2[parent].push_back(curr_node);
        fruit_day2[curr_node]=fruit_day[node];
        fruit_juice2[curr_node]=fruit_juice[node];
        parent=curr_node++;
    }
    
    for(int ch:children[node]){
        init_node(ch,parent);
    }
}

void get(int node){
    dp[node]=IncreasingArray();
    for(int ch:children2[node])
        get(ch);
    
    ll res=fruit_juice2[node];
    for(int ch:children2[node])
        res+=dp[ch].get(fruit_day2[node]);
    
    int biggest_child=-1;
    for(int ch:children2[node])
        if(biggest_child==-1||dp[biggest_child].size()<dp[ch].size())
            biggest_child=ch;
    if(biggest_child!=-1)
        dp[biggest_child].swap_with(dp[node]);
    
    for(int ch:children2[node])
        dp[node].add_array(dp[ch]);
    
    dp[node].add_bound(fruit_day2[node],res);
}

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    //freopen("speeding.in","r",stdin);
    //freopen("speeding.out","w",stdout);
    
    cin>>n>>m>>k;
    for(int i=1;i<n;i++){
        int par;
        cin>>par;
        par--;
        children[par].push_back(i);
    }
    
    for(int i=0;i<m;i++){
        int v,d,w;
        cin>>v>>d>>w;
        v--;
        fruit_day[v]=d;
        fruit_juice[v]=w;
    }
    
    init_node(0,0);
    set<int>s;
    for(int i=0;i<curr_node;i++)
        s.insert(fruit_day2[i]);
    vector<int>v(s.begin(),s.end());
    max_day=(int)v.size();
    unordered_map<int,int>m;
    for(int i=0;i<max_day;i++)
        m[v[i]]=i;
    for(int i=0;i<curr_node;i++)
        fruit_day2[i]=m[fruit_day2[i]];
    
    
    get(0);
    cout<<dp[0].get(max_day-1)<<"\n";
    
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35556 KB Output is correct
2 Correct 30 ms 35564 KB Output is correct
3 Correct 28 ms 35540 KB Output is correct
4 Correct 27 ms 35564 KB Output is correct
5 Correct 28 ms 35568 KB Output is correct
6 Correct 28 ms 35448 KB Output is correct
7 Correct 28 ms 35488 KB Output is correct
8 Correct 27 ms 35540 KB Output is correct
9 Correct 34 ms 35496 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 58976 KB Output is correct
2 Correct 104 ms 57492 KB Output is correct
3 Correct 320 ms 112344 KB Output is correct
4 Correct 306 ms 111668 KB Output is correct
5 Correct 301 ms 112508 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35864 KB Output is correct
2 Correct 30 ms 35804 KB Output is correct
3 Correct 27 ms 35796 KB Output is correct
4 Correct 191 ms 86464 KB Output is correct
5 Correct 153 ms 86436 KB Output is correct
6 Correct 566 ms 86380 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 76432 KB Output is correct
2 Correct 181 ms 78576 KB Output is correct
3 Correct 138 ms 69220 KB Output is correct
4 Correct 243 ms 102936 KB Output is correct
5 Correct 139 ms 73280 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35556 KB Output is correct
2 Correct 30 ms 35564 KB Output is correct
3 Correct 28 ms 35540 KB Output is correct
4 Correct 27 ms 35564 KB Output is correct
5 Correct 28 ms 35568 KB Output is correct
6 Correct 28 ms 35448 KB Output is correct
7 Correct 28 ms 35488 KB Output is correct
8 Correct 27 ms 35540 KB Output is correct
9 Correct 34 ms 35496 KB Output is correct
10 Correct 227 ms 82292 KB Output is correct
11 Correct 223 ms 79872 KB Output is correct
12 Correct 147 ms 68580 KB Output is correct
13 Correct 239 ms 102296 KB Output is correct
14 Correct 123 ms 72664 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 36696 KB Output is correct
2 Correct 73 ms 39068 KB Output is correct
3 Correct 51 ms 39172 KB Output is correct
4 Correct 51 ms 39360 KB Output is correct
5 Correct 39 ms 37732 KB Output is correct
6 Correct 48 ms 39500 KB Output is correct
7 Correct 48 ms 40976 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35556 KB Output is correct
2 Correct 30 ms 35564 KB Output is correct
3 Correct 28 ms 35540 KB Output is correct
4 Correct 27 ms 35564 KB Output is correct
5 Correct 28 ms 35568 KB Output is correct
6 Correct 28 ms 35448 KB Output is correct
7 Correct 28 ms 35488 KB Output is correct
8 Correct 27 ms 35540 KB Output is correct
9 Correct 34 ms 35496 KB Output is correct
10 Correct 28 ms 35864 KB Output is correct
11 Correct 30 ms 35804 KB Output is correct
12 Correct 27 ms 35796 KB Output is correct
13 Correct 191 ms 86464 KB Output is correct
14 Correct 153 ms 86436 KB Output is correct
15 Correct 566 ms 86380 KB Output is correct
16 Correct 227 ms 82292 KB Output is correct
17 Correct 223 ms 79872 KB Output is correct
18 Correct 147 ms 68580 KB Output is correct
19 Correct 239 ms 102296 KB Output is correct
20 Correct 123 ms 72664 KB Output is correct
21 Correct 81 ms 51148 KB Output is correct
22 Correct 189 ms 77608 KB Output is correct
23 Correct 204 ms 94700 KB Output is correct
24 Correct 381 ms 155084 KB Output is correct
25 Correct 308 ms 110964 KB Output is correct
26 Correct 283 ms 98992 KB Output is correct
27 Correct 275 ms 79680 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35556 KB Output is correct
2 Correct 30 ms 35564 KB Output is correct
3 Correct 28 ms 35540 KB Output is correct
4 Correct 27 ms 35564 KB Output is correct
5 Correct 28 ms 35568 KB Output is correct
6 Correct 28 ms 35448 KB Output is correct
7 Correct 28 ms 35488 KB Output is correct
8 Correct 27 ms 35540 KB Output is correct
9 Correct 34 ms 35496 KB Output is correct
10 Correct 122 ms 58976 KB Output is correct
11 Correct 104 ms 57492 KB Output is correct
12 Correct 320 ms 112344 KB Output is correct
13 Correct 306 ms 111668 KB Output is correct
14 Correct 301 ms 112508 KB Output is correct
15 Correct 28 ms 35864 KB Output is correct
16 Correct 30 ms 35804 KB Output is correct
17 Correct 27 ms 35796 KB Output is correct
18 Correct 191 ms 86464 KB Output is correct
19 Correct 153 ms 86436 KB Output is correct
20 Correct 566 ms 86380 KB Output is correct
21 Correct 281 ms 76432 KB Output is correct
22 Correct 181 ms 78576 KB Output is correct
23 Correct 138 ms 69220 KB Output is correct
24 Correct 243 ms 102936 KB Output is correct
25 Correct 139 ms 73280 KB Output is correct
26 Correct 227 ms 82292 KB Output is correct
27 Correct 223 ms 79872 KB Output is correct
28 Correct 147 ms 68580 KB Output is correct
29 Correct 239 ms 102296 KB Output is correct
30 Correct 123 ms 72664 KB Output is correct
31 Correct 37 ms 36696 KB Output is correct
32 Correct 73 ms 39068 KB Output is correct
33 Correct 51 ms 39172 KB Output is correct
34 Correct 51 ms 39360 KB Output is correct
35 Correct 39 ms 37732 KB Output is correct
36 Correct 48 ms 39500 KB Output is correct
37 Correct 48 ms 40976 KB Output is correct
38 Correct 81 ms 51148 KB Output is correct
39 Correct 189 ms 77608 KB Output is correct
40 Correct 204 ms 94700 KB Output is correct
41 Correct 381 ms 155084 KB Output is correct
42 Correct 308 ms 110964 KB Output is correct
43 Correct 283 ms 98992 KB Output is correct
44 Correct 275 ms 79680 KB Output is correct
45 Correct 85 ms 51876 KB Output is correct
46 Correct 174 ms 78572 KB Output is correct
47 Correct 214 ms 95228 KB Output is correct
48 Correct 375 ms 161900 KB Output is correct
49 Correct 298 ms 111656 KB Output is correct
50 Correct 289 ms 99756 KB Output is correct
51 Correct 297 ms 80480 KB Output is correct