oj.uz

Submission #240674

# Submission time Handle Problem Language Result Execution time Memory
240674 2020-06-20T15:08:39 Z karma Magic Tree (CEOI19_magictree) C++14
0 / 100
 2000 ms 618784 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 29304 KB Output is correct
2 Execution timed out 2107 ms 618784 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 10880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 20356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 8576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -