Submission #240674

#	Time	Username	Problem	Language	Result	Execution time	Memory
240674		karma	Magic Tree (CEOI19_magictree)	C++14	0 / 100	2107 ms	618784 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, sz[N];
vector<int> adj[N];
pii fr[N];
map<int, ll> f[N];

void dfs(int u) {
    sz[u] = 1;
    for(int v: adj[u]) {
        dfs(v);
        sz[u] += sz[v];
    }
    sort(adj[u].begin(), adj[u].end(), [&](const int& x, const int& y){
            return f[x].size() < f[y].size();
         });
    for(int v: adj[u]) {
        for(auto ff: f[v]) {
            auto it = f[u].upper_bound(ff.fi);
            if(it == f[u].begin()) f[u].emplace(ff.fi, 0);
            else {
                it = prev(it);
                if(it->fi != ff.fi) f[u].emplace(ff.fi, it->se);
            }
        }
        for(auto& ff: f[u]) {
            auto it = f[v].upper_bound(ff.fi);
            if(it == f[v].begin()) continue;
            it = prev(it);
            ff.se += it->se;
        }
    }
    if(fr[u].fi) {
        ll ans = fr[u].se;
        auto it = f[u].lower_bound(fr[u].fi);
        if(it == f[u].end()) f[u].emplace(fr[u].fi, ans);
        else if(it->fi == fr[u].fi) it->se += ans;
        else f[u].emplace(fr[u].fi, ans + prev(it)->se);
        while(1) {
            auto it = f[u].upper_bound(fr[u].fi);
            if(it == f[u].end() || it->se > ans) break;
            f[u].erase(it);
        }
    }
}

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 = max(res, ff.se);
    cout << res;
}

Compilation message (stderr)

magictree.cpp: In function 'int32_t main()':
magictree.cpp:63: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:64: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: 0 / 6
• Subtask 2: 0 / 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