oj.uz

Submission #242294

# Submission time Handle Problem Language Result Execution time Memory
242294 2020-06-27T08:25:06 Z dwsc Magic Tree (CEOI19_magictree) C++14
34 / 100
 2000 ms 797048 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(){
    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";
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < temp.size(); j++) memo[i][j] = -1;
    }
    cout << dp(1,temp.size()-1);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j < temp.size(); j++) assert(dp(i,j)>= dp(i,j-1));
    }
}

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:41:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < temp.size(); j++) memo[i][j] = -1;
                         ~~^~~~~~~~~~~~~
magictree.cpp:45:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < temp.size(); j++) assert(dp(i,j)>= dp(i,j-1));
                         ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 7 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 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 2720 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2129 ms 777388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 9984 KB Output is correct
2 Correct 15 ms 9856 KB Output is correct
3 Correct 15 ms 9932 KB Output is correct
4 Execution timed out 2107 ms 288704 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 410088 KB Output is correct
2 Correct 349 ms 408428 KB Output is correct
3 Correct 372 ms 412648 KB Output is correct
4 Correct 318 ms 409064 KB Output is correct
5 Correct 357 ms 416112 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 7 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 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 2720 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct
10 Correct 399 ms 424104 KB Output is correct
11 Correct 356 ms 416360 KB Output is correct
12 Correct 369 ms 426596 KB Output is correct
13 Correct 389 ms 423148 KB Output is correct
14 Correct 360 ms 430064 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 161656 KB Output is correct
2 Correct 1357 ms 796984 KB Output is correct
3 Correct 1344 ms 797048 KB Output is correct
4 Correct 1606 ms 797048 KB Output is correct
5 Execution timed out 2111 ms 796008 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 7 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 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 2720 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct
10 Correct 18 ms 9984 KB Output is correct
11 Correct 15 ms 9856 KB Output is correct
12 Correct 15 ms 9932 KB Output is correct
13 Execution timed out 2107 ms 288704 KB Time limit exceeded
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 7 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 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 2720 KB Output is correct
9 Correct 7 ms 2816 KB Output is correct
10 Execution timed out 2129 ms 777388 KB Time limit exceeded
11 Halted 0 ms 0 KB -