oj.uz

Submission #240676

# Submission time Handle Problem Language Result Execution time Memory
240676 2020-06-20T15:18:12 Z karma Magic Tree (CEOI19_magictree) C++14
47 / 100
 2000 ms 625044 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;
vector<int> adj[N];
pii fr[N];
map<int, ll> f[N];

void dfs(int u) {
    for(int v: adj[u]) dfs(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].upper_bound(fr[u].fi);
        if(it == f[u].begin()) f[u].emplace(fr[u].fi, ans);
        else {
            it = prev(it);
            if(it->fi == fr[u].fi) it->se += ans, ans = it->se;
            else f[u].emplace(fr[u].fi, ans += 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:62: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:63: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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 9 ms 7424 KB Output is correct
9 Correct 9 ms 7424 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 29048 KB Output is correct
2 Execution timed out 2136 ms 625044 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7808 KB Output is correct
2 Correct 13 ms 9088 KB Output is correct
3 Correct 49 ms 19960 KB Output is correct
4 Correct 145 ms 59896 KB Output is correct
5 Execution timed out 2119 ms 566392 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 18040 KB Output is correct
2 Correct 100 ms 17784 KB Output is correct
3 Correct 96 ms 28920 KB Output is correct
4 Correct 60 ms 15984 KB Output is correct
5 Correct 88 ms 38520 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 9 ms 7424 KB Output is correct
9 Correct 9 ms 7424 KB Output is correct
10 Correct 136 ms 26104 KB Output is correct
11 Correct 127 ms 23928 KB Output is correct
12 Correct 330 ms 115448 KB Output is correct
13 Correct 67 ms 15348 KB Output is correct
14 Correct 329 ms 143020 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8448 KB Output is correct
2 Correct 46 ms 10976 KB Output is correct
3 Correct 44 ms 10872 KB Output is correct
4 Correct 59 ms 11128 KB Output is correct
5 Correct 26 ms 8956 KB Output is correct
6 Correct 888 ms 271864 KB Output is correct
7 Correct 888 ms 301688 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 9 ms 7424 KB Output is correct
9 Correct 9 ms 7424 KB Output is correct
10 Correct 9 ms 7808 KB Output is correct
11 Correct 13 ms 9088 KB Output is correct
12 Correct 49 ms 19960 KB Output is correct
13 Correct 145 ms 59896 KB Output is correct
14 Execution timed out 2119 ms 566392 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 9 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 9 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 9 ms 7424 KB Output is correct
9 Correct 9 ms 7424 KB Output is correct
10 Correct 163 ms 29048 KB Output is correct
11 Execution timed out 2136 ms 625044 KB Time limit exceeded
12 Halted 0 ms 0 KB -