oj.uz

Submission #242311

# Submission time Handle Problem Language Result Execution time Memory
242311 2020-06-27T08:40:46 Z dwsc Magic Tree (CEOI19_magictree) C++14
37 / 100
 346 ms 425324 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
vector<int> adj[100010];
int ripe[100010];
int weight[100010];
int memo[100010][1010];
int dp(int u,int j){
    if (j == 0) return 0;
    if (memo[u][j] != -1) return memo[u][j];
    int s = 0;
    for (int i = 0; i < adj[u].size(); i++){
        int v = adj[u][i];
        s += dp(v,j);
    }
    if (j == ripe[u]) s += weight[u];
    return memo[u][j] = max(s,dp(u,j-1));
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++){
        int p;
        cin >> p;
        adj[p].push_back(i);
    }
    vector<int> temp;
    temp.push_back(0);
    for (int i = 0; i < m; i++){
        int v,d,w;
        cin >> v >> d >> w;
        ripe[v] = d;
        weight[v] = w;
        temp.push_back(d);
    }
    sort(temp.begin(),temp.end());
    temp.erase(unique(temp.begin(),temp.end()),temp.end());
    for (int i = 1; i <= n; i++) ripe[i] = lower_bound(temp.begin(),temp.end(),ripe[i])-temp.begin();
    //for (int i = 1; i <= n; i++) cout << ripe[i] << "\n";
    if (k <= 20){
    for (int i = n; i >= 1; i--){
        for (int j = 1; j < temp.size(); j++){
            for (int x = 0; x < adj[i].size(); x++){
                int v = adj[i][x];
                memo[i][j] += memo[v][j];
            }
            if (j == ripe[i]) memo[i][j] += weight[i];
            memo[i][j] = max(memo[i][j],memo[i][j-1]);
        }
    }
    cout << dp(1,temp.size()-1);
    }
    else{
        int ans = 0;
        for (int i = 1; i <= n; i++) ans += weight[i];
        cout << ans;
    }
}

Compilation message

magictree.cpp: In function 'long long int dp(long long int, long long int)':
magictree.cpp:13:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adj[u].size(); i++){
                     ~~^~~~~~~~~~~~~~~
magictree.cpp: At global scope:
magictree.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
magictree.cpp: In function 'int main()':
magictree.cpp:44:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < temp.size(); j++){
                         ~~^~~~~~~~~~~~~
magictree.cpp:45:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int x = 0; x < adj[i].size(); x++){
                             ~~^~~~~~~~~~~~~~~

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 6 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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6264 KB Output is correct
2 Correct 37 ms 6516 KB Output is correct
3 Correct 72 ms 6380 KB Output is correct
4 Correct 63 ms 6640 KB Output is correct
5 Correct 70 ms 6380 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 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 323 ms 410124 KB Output is correct
2 Correct 326 ms 408644 KB Output is correct
3 Correct 310 ms 410844 KB Output is correct
4 Correct 287 ms 408944 KB Output is correct
5 Correct 314 ms 411372 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 6 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 342 ms 424172 KB Output is correct
11 Correct 319 ms 416364 KB Output is correct
12 Correct 346 ms 424808 KB Output is correct
13 Correct 341 ms 423028 KB Output is correct
14 Correct 319 ms 425324 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3456 KB Output isn't correct
2 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 6 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 6 ms 2688 KB Output isn't correct
11 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 6 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 39 ms 6264 KB Output is correct
11 Correct 37 ms 6516 KB Output is correct
12 Correct 72 ms 6380 KB Output is correct
13 Correct 63 ms 6640 KB Output is correct
14 Correct 70 ms 6380 KB Output is correct
15 Incorrect 6 ms 2688 KB Output isn't correct
16 Halted 0 ms 0 KB -