Submission #771876

#	Time	Username	Problem	Language	Result	Execution time	Memory
771876		JakobZorz	Magic Tree (CEOI19_magictree)	C++17	100 / 100	566 ms	161900 KiB

magictree

#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 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17