oj.uz

Submission #242274

# Submission time Handle Problem Language Result Execution time Memory
242274 2020-06-27T08:00:13 Z lyc Magic Tree (CEOI19_magictree) C++14
6 / 100
 2000 ms 582368 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 res[mxN][1005];

ll dp(int u, int k) {
    bool take = (fruit[u] != ii(-1,-1) && fruit[u].first <= k);
    ll s1 = 0, s2 = (take ? fruit[u].second : 0);
    for (int v : al[u]) {
        s1 += dp(v,k);
        if (take) s2 += dp(v,fruit[u].first);
    }
    return res[u][k] = max(s1,s2);
}

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();
    }

    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 10 ms 2816 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 231 ms 406624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9856 KB Output is correct
2 Execution timed out 2082 ms 4728 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 408880 KB Output is correct
2 Execution timed out 2109 ms 237424 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
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 10 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Correct 450 ms 422104 KB Output is correct
11 Correct 499 ms 414544 KB Output is correct
12 Execution timed out 2025 ms 10064 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 102520 KB Output is correct
2 Correct 274 ms 499868 KB Output is correct
3 Correct 251 ms 424440 KB Output is correct
4 Correct 240 ms 420856 KB Output is correct
5 Correct 276 ms 582368 KB Output is correct
6 Execution timed out 2087 ms 82028 KB Time limit exceeded
7 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 10 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Correct 17 ms 9856 KB Output is correct
11 Execution timed out 2082 ms 4728 KB Time limit exceeded
12 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 10 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Incorrect 231 ms 406624 KB Output isn't correct
11 Halted 0 ms 0 KB -