oj.uz

Submission #723774

# Submission time Handle Problem Language Result Execution time Memory
723774 2023-04-14T09:47:55 Z Mr_Husanboy Magic Tree (CEOI19_magictree) C++17
48 / 100
 609 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9;

template<typename T>
int len(T &a){
    return a.size();
}

struct Segtree{
    struct node{
        int mx = 0;
        void set(int x){
            mx = max(mx, x);
        }
        node(int x){mx = x;}
        node(){mx = 0;};
    };

    node merge(node a, node b){
        return node(max(a.mx, b.mx));
    }

    vector<node> t;
    int n;
    void init(int _n){
        n = _n;
        t.resize(4 * n, node());
    }

    void upd(int x, int lx, int rx, int ind, int val){
        if(lx == rx){
            t[x].set(val); return;
        }
        int m = (lx + rx) / 2;
        if(ind <= m){
            upd(x * 2, lx, m, ind, val);
        }else
            upd(x * 2 + 1, m + 1, rx, ind, val);
        t[x] = merge(t[x * 2], t[x * 2 + 1]);
    }

    node get(int x, int lx, int rx, int l, int r){
        if(l <= lx && rx <= r) return t[x];
        if(r < lx || rx < l){
            return {0};
        }
        int m = (lx + rx) / 2;
        return merge(get(x * 2, lx, m, l, r), get(x * 2 + 1, m + 1, rx, l, r));
    }

    void upd(int ind, int val){
        upd(1, 0, n - 1, ind, val);
    }

    node get(int l, int r){
        return get(1, 0, n - 1, l, r);
    }
};

void sub3(int &n, int &m, int &k, vector<int> p,
    vector<int> &v, vector<int> &day, vector<int> &cost){
    //cout << "start" << endl;
    for(int i = 1; i < n; i ++){
        if(p[i] != i - 1) return;
    }
    for(int i = 0; i < m; i ++){
        if(cost[i] != 1) return;
    }
    vector<int> fr(n);
    for(int i = 0; i < m; i ++){
        fr[v[i]] = day[i];
    }
    Segtree t; t.init(k + 1);
    int ans = 0;
    for(int i = n - 1; i > 0; i --){
        if(fr[i] == 0) continue;
        int mx = t.get(1, fr[i]).mx + 1;
        ans = max(ans, mx);
        t.upd(fr[i], mx);
    }
    cout << ans; exit(0); 
    cout << endl;
}

void sub2(int &n, int &m, int &k, vector<int> p,
    vector<int> &v, vector<int> &day, vector<int> &cost){
    //cout << "start" << endl;
    vector<vector<int>> g(n);
    for(int i = 1; i < n; i ++){
        g[p[i]].push_back(i);
    }
    ll ans = 0;
    for(int i = 0; i < m; i ++){
        if(len(g[v[i]])){return;}
        ans += cost[i];
    }
    cout << ans; exit(0);

}


void sub5(int &n, int &m, int &k, vector<int> p,
    vector<int> &v, vector<int> &day, vector<int> &cost){
    //cout << "start" << endl;

    vector<vector<int>> g(n);
    for(int i = 1; i < n; i ++){
        g[p[i]].push_back(i);
    }
    vector<ll> fr(n), c(n);
    for(int i = 0; i < m; i ++){
        fr[v[i]] = day[i];
        c[v[i]] = cost[i];
    }
    vector<vector<ll>> dp(n + 1, vector<ll> (k + 1, 0)), 
                    pref(n + 1, vector<ll> (k + 1, 0));
    auto dfs = [&](auto &dfs, int i)->void{
        //cout << i + 1 << endl;
        for(auto u : g[i]){
            dfs(dfs, u);
        }
        for(int j = 1; j <= k; j ++){
            ll s = (j == fr[i] ? c[i] : 0);
            for(auto u : g[i]){
                s += pref[u][j];
            }
            dp[i][j] = s;
            pref[i][j] = max(pref[i][j - 1], dp[i][j]);
        }
    };
    dfs(dfs, 0);
    //cout << "d" << endl;
    ll mx = 0;
    for(int i = 0; i < n; i ++){
        for(int j = 1; j <= k; j++){
            mx = max(mx, dp[i][j]);
        }
    }
    cout << mx << endl;; 
    exit(0);
}

void solve(){
    int n, m, k; cin >> n >> m >> k;
    vector<int> p(n), v(m), day(m), cost(m);
    for(int i = 1; i < n; i ++){
        cin >> p[i]; p[i] --;
    }
    for(int i = 0; i < m; i ++){
        cin >> v[i] >> day[i] >> cost[i];
        v[i] --;
    }
    sub2(n, m, k, p, v, day, cost);
    sub3(n, m, k, p, v, day, cost);
    sub5(n, m, k, p, v, day, cost);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int testcases = 1;

    while(testcases --){
        solve();
        if(testcases) cout << '\n';
        #ifdef LOCAL
        else cout << '\n';
        cout << "__________________________" << endl;
        #endif
    }
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5580 KB Output is correct
2 Correct 18 ms 6668 KB Output is correct
3 Correct 37 ms 5600 KB Output is correct
4 Correct 32 ms 5840 KB Output is correct
5 Correct 37 ms 5948 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 324 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 62 ms 8812 KB Output is correct
5 Correct 60 ms 9560 KB Output is correct
6 Correct 67 ms 9680 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 19560 KB Output is correct
2 Correct 88 ms 20732 KB Output is correct
3 Correct 64 ms 23460 KB Output is correct
4 Correct 42 ms 19172 KB Output is correct
5 Correct 55 ms 26664 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 120 ms 47224 KB Output is correct
11 Correct 100 ms 32544 KB Output is correct
12 Correct 88 ms 50868 KB Output is correct
13 Correct 84 ms 46624 KB Output is correct
14 Correct 38 ms 9024 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 609 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 62 ms 8812 KB Output is correct
14 Correct 60 ms 9560 KB Output is correct
15 Correct 67 ms 9680 KB Output is correct
16 Correct 120 ms 47224 KB Output is correct
17 Correct 100 ms 32544 KB Output is correct
18 Correct 88 ms 50868 KB Output is correct
19 Correct 84 ms 46624 KB Output is correct
20 Correct 38 ms 9024 KB Output is correct
21 Correct 484 ms 629924 KB Output is correct
22 Runtime error 442 ms 1048576 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 27 ms 5580 KB Output is correct
11 Correct 18 ms 6668 KB Output is correct
12 Correct 37 ms 5600 KB Output is correct
13 Correct 32 ms 5840 KB Output is correct
14 Correct 37 ms 5948 KB Output is correct
15 Correct 2 ms 324 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 62 ms 8812 KB Output is correct
19 Correct 60 ms 9560 KB Output is correct
20 Correct 67 ms 9680 KB Output is correct
21 Correct 91 ms 19560 KB Output is correct
22 Correct 88 ms 20732 KB Output is correct
23 Correct 64 ms 23460 KB Output is correct
24 Correct 42 ms 19172 KB Output is correct
25 Correct 55 ms 26664 KB Output is correct
26 Correct 120 ms 47224 KB Output is correct
27 Correct 100 ms 32544 KB Output is correct
28 Correct 88 ms 50868 KB Output is correct
29 Correct 84 ms 46624 KB Output is correct
30 Correct 38 ms 9024 KB Output is correct
31 Runtime error 609 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -