Submission #1126186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126186		luvna	Magic Tree (CEOI19_magictree)	C++20	100 / 100	118 ms	48968 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{

    bool keep[N];
    pii prep[N];
    map<int, ll> mp[N];

    void dfs(int u){
        for(int v : g[u]){
            dfs(v);
            if(sz(mp[u]) < sz(mp[v])) swap(mp[u], mp[v]);
            for(auto [date, p] : mp[v]) mp[u][date] += p;
            mp[v].clear();//opt mem
        }

        //lis like subtask 1

        if(keep[u]){
            int dateU = prep[u].fi;
            ll sum = prep[u].se;
            mp[u][dateU] += prep[u].se;

            while(true){
                auto id = mp[u].upper_bound(dateU);

                if(id == mp[u].end()) break;

                if((*id).se <= sum){
                    sum -= (*id).se; // profit +sum - (value <= sum)
                    mp[u].erase(id);
                }
                else{// value > sum -> rather keep value than sum
                    id -> se -= sum;
                    break;
                }
            }
        }
    }

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

        dfs(1);

        ll ans = 0;

        for(auto [date, p] : mp[1]) ans += p;

        cout << ans << 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();
}

/*
6 5 5
1
1
3
3
5
2 1 13
4 5 15
1 4 3
3 1 17
6 1 11
*/

Compilation message (stderr)

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

• 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