oj.uz

Submission #519741

# Submission time Handle Problem Language Result Execution time Memory
519741 2022-01-27T08:08:31 Z Monarchuwu Magic Tree (CEOI19_magictree) C++17
61 / 100
 341 ms 702160 KB 
// nén cây và k dựa vào m
// O(n * min(m, k))
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 1e5 + 9;
int n, m, k;
int p[N];
pii fruit[N];
vector<int> g[N];

namespace sub2 {
    bool check() {
        for (int i = 2; i <= n; ++i)
            if (g[i].size() && fruit[i].ff) return false;
        return true;
    }
    void solve() {
        ll sum(0);
        for (int i = 2; i <= n; ++i)
            sum += fruit[i].ss;
        cout << sum << '\n';
    }
}

namespace sub3 {
    bool check() {
        for (int i = 2; i <= n; ++i)
            if (p[i] != i - 1 || fruit[i].ss > 1) return false;
        return true;
    }
    int lis[N];
    void solve() {
        int cnt(0);
        for (int i = n, pos; i; --i) if (fruit[i].ff) {
            pos = upper_bound(lis + 1, lis + cnt + 1, fruit[i].ff) - lis;
            if (cnt < pos) cnt = pos;
            lis[pos] = fruit[i].ff;
        }
        cout << cnt << '\n';
    }
}

ll dp[N][1003];
namespace sub1456 {
    int cnt(0), b[N];
    void dfs(int u) {
        for (int v : g[u]) {
            dfs(v);
            for (int i = 1; i < cnt; ++i)
                dp[u][i] += dp[v][i];
        }
        if (fruit[u].ff) {
            dp[u][fruit[u].ff] += fruit[u].ss;
            for (int i = fruit[u].ff + 1; i < cnt; ++i)
                dp[u][i] = max(dp[u][i], dp[u][fruit[u].ff]);
        }
    }
    void solve() {
        for (int i = 1; i <= n; ++i) if (fruit[i].ff) b[++cnt] = fruit[i].ff;
        sort(b + 1, b + cnt + 1);
        cnt = unique(b + 1, b + cnt + 1) - b;
        for (int i = 1; i <= n; ++i)
            if (fruit[i].ff) fruit[i].ff = lower_bound(b + 1, b + cnt, fruit[i].ff) - b;

        dfs(1);
        cout << *max_element(dp[1], dp[1] + cnt) << '\n';
    }
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 2; i <= n; ++i) {
        cin >> p[i];
        g[p[i]].push_back(i);
    }
    for (int i = 0, v; i < m; ++i) {
        cin >> v;
        cin >> fruit[v].ff >> fruit[v].ss;
    }

    if (sub2::check()) sub2::solve();
    else if (sub3::check()) sub3::solve();
    else sub1456::solve();
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5792 KB Output is correct
2 Correct 19 ms 6324 KB Output is correct
3 Correct 34 ms 5060 KB Output is correct
4 Correct 29 ms 4956 KB Output is correct
5 Correct 32 ms 5124 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 32 ms 7632 KB Output is correct
5 Correct 32 ms 7948 KB Output is correct
6 Correct 36 ms 7676 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 387776 KB Output is correct
2 Correct 219 ms 389636 KB Output is correct
3 Correct 194 ms 406216 KB Output is correct
4 Correct 212 ms 368452 KB Output is correct
5 Correct 173 ms 419472 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 1 ms 2680 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2684 KB Output is correct
10 Correct 239 ms 399316 KB Output is correct
11 Correct 240 ms 394364 KB Output is correct
12 Correct 197 ms 417816 KB Output is correct
13 Correct 216 ms 373828 KB Output is correct
14 Correct 34 ms 8376 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 91972 KB Output is correct
2 Correct 285 ms 437400 KB Output is correct
3 Correct 287 ms 436764 KB Output is correct
4 Correct 304 ms 467296 KB Output is correct
5 Correct 151 ms 13968 KB Output is correct
6 Correct 278 ms 419860 KB Output is correct
7 Correct 341 ms 702160 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 1 ms 2680 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2684 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 32 ms 7632 KB Output is correct
14 Correct 32 ms 7948 KB Output is correct
15 Correct 36 ms 7676 KB Output is correct
16 Correct 239 ms 399316 KB Output is correct
17 Correct 240 ms 394364 KB Output is correct
18 Correct 197 ms 417816 KB Output is correct
19 Correct 216 ms 373828 KB Output is correct
20 Correct 34 ms 8376 KB Output is correct
21 Incorrect 135 ms 156260 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2684 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2680 KB Output is correct
7 Correct 1 ms 2680 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 2 ms 2684 KB Output is correct
10 Correct 22 ms 5792 KB Output is correct
11 Correct 19 ms 6324 KB Output is correct
12 Correct 34 ms 5060 KB Output is correct
13 Correct 29 ms 4956 KB Output is correct
14 Correct 32 ms 5124 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 32 ms 7632 KB Output is correct
19 Correct 32 ms 7948 KB Output is correct
20 Correct 36 ms 7676 KB Output is correct
21 Correct 217 ms 387776 KB Output is correct
22 Correct 219 ms 389636 KB Output is correct
23 Correct 194 ms 406216 KB Output is correct
24 Correct 212 ms 368452 KB Output is correct
25 Correct 173 ms 419472 KB Output is correct
26 Correct 239 ms 399316 KB Output is correct
27 Correct 240 ms 394364 KB Output is correct
28 Correct 197 ms 417816 KB Output is correct
29 Correct 216 ms 373828 KB Output is correct
30 Correct 34 ms 8376 KB Output is correct
31 Correct 58 ms 91972 KB Output is correct
32 Correct 285 ms 437400 KB Output is correct
33 Correct 287 ms 436764 KB Output is correct
34 Correct 304 ms 467296 KB Output is correct
35 Correct 151 ms 13968 KB Output is correct
36 Correct 278 ms 419860 KB Output is correct
37 Correct 341 ms 702160 KB Output is correct
38 Incorrect 135 ms 156260 KB Output isn't correct
39 Halted 0 ms 0 KB -