oj.uz

Submission #723681

# Submission time Handle Problem Language Result Execution time Memory
723681 2023-04-14T07:30:32 Z dxz05 Magic Tree (CEOI19_magictree) C++17
34 / 100
 1775 ms 792284 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MP make_pair
const int N = 100500;

struct fenwick{
    vector<int> f;
    fenwick(int n){
        f.resize(n + 2);
    };
    void add(int i, int x){
        i++;
        while (i < (int)f.size()){
            f[i] = max(f[i], x);
            i += (-i) & i;
        }
    }
    int get(int i){
        i++;
        int res = 0;
        while (i > 0){
            res = max(res, f[i]);
            i -= (-i) & i;
        }
        return res;
    }
};

vector<int> g[N];

vector<vector<ll>> dp;
pair<int, int> fruit[N];

void dfs(int v){
    dp[v][fruit[v].first] = fruit[v].second;

    for (int u : g[v]){
        dfs(u);
    }

    for (int t = 1; t < dp[v].size(); t++){
        for (int u : g[v]){
            dp[v][t] += dp[u][t];
        }
    }

    for (int t = 1; t < dp[v].size(); t++) dp[v][t] = max(dp[v][t], dp[v][t - 1]);

}

int LIS(const vector<int> &a){
    int n = (int) a.size();
    fenwick f(2e5);
    int res = 0;
    for (int i = 0; i < n; i++){
        int _dp = f.get(a[i]) + 1;
        f.add(a[i], _dp);
        res = max(res, _dp);
    }
    return res;
}

void solve(){
    int n, m, k;
    cin >> n >> m >> k;

    ll sum = 0;
    bool sub3 = true;
    for (int i = 1; i < n; i++){
        int p;
        cin >> p;
        --p;
        if (p != i - 1) sub3 = false;
        g[p].push_back(i);
    }

    map<int, int> mp;

    vector<int> a(n);
    for (int i = 0; i < m; i++){
        int v, d, w;
        cin >> v >> d >> w;
        --v;
        mp[d];
        fruit[v] = MP(d, w);
        sum += w;
        a[v] = d;
        if (w != 1) sub3 = false;
    }

    if (sub3){
        reverse(all(a));
        cout << LIS(a) << endl;
        return;
    }

    mp[0];
    k = 0;
    for (auto &now : mp){
        now.second = ++k;
    }

    for (int i = 0; i < n; i++){
        fruit[i].first = mp[fruit[i].first];
    }

    if (k > 1000){
        cout << sum << endl;
        return;
    }

    dp.assign(n, vector<ll>(k + 1, 0));

    dfs(0);

    cout << dp[0].back() << endl;

}

int main() {
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    solve();

    return 0;
}

Compilation message

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int t = 1; t < dp[v].size(); t++){
      |                     ~~^~~~~~~~~~~~~~
magictree.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int t = 1; t < dp[v].size(); t++) dp[v][t] = max(dp[v][t], dp[v][t - 1]);
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6244 KB Output is correct
2 Correct 35 ms 7096 KB Output is correct
3 Correct 97 ms 7336 KB Output is correct
4 Correct 92 ms 7176 KB Output is correct
5 Correct 85 ms 7620 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 12940 KB Output is correct
2 Correct 76 ms 11028 KB Output is correct
3 Correct 66 ms 15336 KB Output is correct
4 Correct 40 ms 11392 KB Output is correct
5 Correct 59 ms 18788 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 3 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 88 ms 26856 KB Output is correct
11 Correct 71 ms 19248 KB Output is correct
12 Correct 90 ms 29900 KB Output is correct
13 Correct 84 ms 25860 KB Output is correct
14 Incorrect 40 ms 8268 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 128064 KB Output is correct
2 Correct 673 ms 607824 KB Output is correct
3 Correct 665 ms 610896 KB Output is correct
4 Correct 849 ms 789452 KB Output is correct
5 Correct 1775 ms 788192 KB Output is correct
6 Correct 869 ms 790240 KB Output is correct
7 Correct 937 ms 792284 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 3 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Incorrect 4 ms 3556 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 3 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 39 ms 6244 KB Output is correct
11 Correct 35 ms 7096 KB Output is correct
12 Correct 97 ms 7336 KB Output is correct
13 Correct 92 ms 7176 KB Output is correct
14 Correct 85 ms 7620 KB Output is correct
15 Incorrect 4 ms 3556 KB Output isn't correct
16 Halted 0 ms 0 KB -