oj.uz

Submission #242265

# Submission time Handle Problem Language Result Execution time Memory
242265 2020-06-27T07:53:59 Z lyc Magic Tree (CEOI19_magictree) C++14
34 / 100
 2000 ms 791996 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;
using ii=pair<int,int>;
using pll=pair<ll,ll>;

const int mxN = 1e5+5;
const int mxM = mxN;
const int mxK = 1e5+5;

int N, M, K;
vector<int> al[mxN];
ii fruit[mxN];
vector<int> vals;
ll dp[mxN][1005];

void dfs(int u) {
    for (int v : al[u]) {
        dfs(v);
    }
    FOR(k,0,SZ(vals)-1){
        dp[u][k] = 0;
        for (int v : al[u]) dp[u][k] += dp[v][k];
        if (fruit[u].first <= k) {
            ll sum = fruit[u].second;
            for (int v : al[u]) sum += dp[v][fruit[u].first];
            dp[u][k] = max(dp[u][k],sum);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K;
    FOR(i,2,N){
        int P; cin >> P;
        al[P].push_back(i);
    }
    FOR(i,1,N) fruit[i] = ii(-1,-1);
    FOR(i,1,M){
        int V, D, W; cin >> V >> D >> W;
        fruit[V] = ii(D,W);
        vals.push_back(D);
    }

    vals.push_back(mxK);
    sort(ALL(vals)); vals.resize(unique(ALL(vals))-vals.begin());
    fruit[0] = ii(mxK,0);
    FOR(i,0,N) if (fruit[i] != ii(-1,-1)) {
        fruit[i].first = lower_bound(ALL(vals),fruit[i].first)-vals.begin();
    }

    dfs(1);
    cout << dp[1][SZ(vals)-1] << '\n';
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9856 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 11 ms 9856 KB Output is correct
4 Incorrect 69 ms 13808 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 409008 KB Output is correct
2 Correct 274 ms 410072 KB Output is correct
3 Correct 281 ms 413556 KB Output is correct
4 Correct 222 ms 409204 KB Output is correct
5 Correct 233 ms 417132 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2944 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Correct 319 ms 424220 KB Output is correct
11 Correct 277 ms 416372 KB Output is correct
12 Correct 261 ms 427076 KB Output is correct
13 Correct 289 ms 422772 KB Output is correct
14 Correct 255 ms 430448 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 160632 KB Output is correct
2 Correct 672 ms 791996 KB Output is correct
3 Correct 675 ms 791800 KB Output is correct
4 Correct 765 ms 791908 KB Output is correct
5 Execution timed out 2008 ms 790760 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2944 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Correct 12 ms 9856 KB Output is correct
11 Correct 11 ms 9856 KB Output is correct
12 Correct 11 ms 9856 KB Output is correct
13 Incorrect 69 ms 13808 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2944 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Incorrect 770 ms 597896 KB Output isn't correct
11 Halted 0 ms 0 KB -