Submission #1126165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126165		luvna	Magic Tree (CEOI19_magictree)	C++20	3 / 100	113 ms	32068 KiB

magictree

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 2e5 + 15;

int n, m, k;
int par[N];
vector<int> g[N];
int vert[N], d[N], profit[N];

namespace subtask1{
    bool check(void){
        return n <= 1000 && m <= 1000;
    }

    multiset<pii> ms[N];
    pii prep[N];

    void dfs(int u){
        for(int v : g[u]){
            dfs(v);
            if(sz(ms[v]) > sz(ms[u])) swap(ms[u], ms[v]);
            ms[u].insert(all(ms[v]));
        }

        if(prep[u].fi){
            pii e = prep[u];
            multiset<pii> small;
            multiset<pii> large;
            ll sum = 0;
            for(auto [date, p] : ms[u]){
                if(date <= e.fi) small.insert(pii(date,p));
                else large.insert(pii(date,p)), sum += p;
            }
            ms[u] = small;
            if(e.se >= sum) ms[u].insert(e);
            else ms[u].insert(all(large));
        }
    }

    void main(){
        for(int i = 1; i <= m; i++){
            prep[vert[i]] = pii(d[i], profit[i]);
        }

        dfs(1);

        ll sum = 0;

        for(auto [date, p] : ms[1]) sum += p;

        cout << sum << endl;
    }
}

namespace subtask8{
    int h[N];
    int tin[N], tout[N], timerDFS;
    vector<pair<int,int>> query[N];

    void dfs(int u){
        tin[u] = ++timerDFS;
        for(int v : g[u]){
            h[v] = h[u] + 1;
            dfs(v);
        }
        tout[u] = timerDFS;
    }

    struct SegmentTree{
        int n;
        vector<ll> st, lz;

        SegmentTree() {}

        void init(int _n){
            n = _n;
            st.resize((n << 2) + 15, 0);
            lz.resize((n << 2) + 15, -1);
        }

        void change(int l, int r, int id, ll val){
            st[id] = 1LL*(r-l+1)*val;
            lz[id] = val;
        }

        void down(int l, int r, int id, int mid){
            if(lz[id] != -1){
                change(l,mid,id<<1,lz[id]);
                change(mid+1,r,id<<1|1,lz[id]);
                lz[id] = -1;
            }
        }

        void update(int l, int r, int id, int u, int v, ll val){
            if(r < u || l > v) return;
            if(u <= l && r <= v){
                change(l,r,id,val);
                return;
            }
            int mid = (l+r) >> 1;
            down(l,r,id,mid);
            update(l,mid,id<<1,u,v,val);
            update(mid+1,r,id<<1|1,u,v,val);
            st[id] = st[id<<1] + st[id<<1|1];
        }

        ll get(int l, int r, int id, int u, int v){
            if(r < u || l > v) return 0;
            if(l == r) return st[id];
            int mid = (l+r) >> 1;
            down(l,r,id,mid);
            return get(l,mid,id<<1,u,v) + get(mid+1,r,id<<1|1,u,v);
        }

        void update(int l, int r, ll val){
            update(1,n,1,l,r,val);
        }

        ll get(int l, int r){
            return get(1,n,1,l,r);
        }
    } st;


    void main(){
        dfs(1);

        for(int i = 1; i <= m; i++){
            query[d[i]].push_back(pii(vert[i], profit[i]));
        }

        for(int i = 1; i <= k; i++){
            sort(all(query[i]), [&](pii a, pii b){
                return h[a.fi] > h[b.fi];
            });
        }

        st.init(n);

        for(int i = k; i >= 1; i--){
            for(auto e : query[i]){
                int u; ll p; tie(u,p) = e;
                ll sum = st.get(tin[u], tout[u]);
                if(p > sum){
                    st.update(tin[u],tout[u],0);
                    st.update(tin[u],tin[u],p);
                }
            }
        }

        cout << st.get(1,n) << endl;
    }
}

void solve(){
    cin >> n >> m >> k;

    for(int v = 2; v <= n; v++){
        int u; cin >> u;
        g[u].push_back(v);
        par[v] = u;
    }

    for(int i = 1; i <= m; i++){
        cin >> vert[i] >> d[i] >> profit[i];
    }

    /*if(subtask1::check()) subtask1::main();
    else*/ subtask8::main();
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:201:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:202:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 3 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17