oj.uz

답안 #242274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 231 ms 406624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -