Submission #240678

#	Time	Username	Problem	Language	Result	Execution time	Memory
240678		karma	Magic Tree (CEOI19_magictree)	C++14	100 / 100	165 ms	36984 KiB

magictree

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = int(1e5) + 10;
typedef pair<int, int> pii;

int n, m, k, p;
vector<int> adj[N];
pii fr[N];
map<int, ll> f[N];

void dfs(int u) {
    for(int v: adj[u]) {
        dfs(v);
        if(f[u].size() < f[v].size()) f[u].swap(f[v]);
        for(auto& ff: f[v]) f[u][ff.fi] += ff.se;
    }
    if(fr[u].fi) {
        ll tmp = 0;
        while(1) {
            auto it = f[u].upper_bound(fr[u].fi);
            if(it == f[u].end()) break;
            if(it->se + tmp > fr[u].se) {
                it->se += (tmp - fr[u].se);
                break;
            }
            tmp += it->se;
            f[u].erase(it);
        }
        f[u][fr[u].fi] += fr[u].se;
    }
    //cout << u << '\n';
    //for(auto ff: f[u]) cout << ff.fi << ' ' << ff.se << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> m >> k;
    for(int i = 2; i <= n; ++i) {
        cin >> p;
        adj[p].pb(i);
    }
    for(int v, d, w, i = 1; i <= m; ++i) {
        cin >> v >> d >> w;
        fr[v] = mp(d, w);
    }
    dfs(1);
    ll res = 0;
    for(auto ff: f[1]) res += ff.se;
    cout << res;
}

Compilation message (stderr)

magictree.cpp: In function 'int32_t main()':
magictree.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         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