oj.uz

Submission #242298

# Submission time Handle Problem Language Result Execution time Memory
242298 2020-06-27T08:28:40 Z dwsc Magic Tree (CEOI19_magictree) C++14
34 / 100
 2000 ms 796792 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 = 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);
}

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 = 1; j < temp.size(); j++){
                         ~~^~~~~~~~~~~~~
magictree.cpp:42: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
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9856 KB Output is correct
2 Correct 13 ms 9856 KB Output is correct
3 Correct 14 ms 9856 KB Output is correct
4 Execution timed out 2047 ms 68960 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 409988 KB Output is correct
2 Correct 407 ms 408552 KB Output is correct
3 Correct 412 ms 410728 KB Output is correct
4 Correct 415 ms 408936 KB Output is correct
5 Correct 409 ms 411244 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 426 ms 424424 KB Output is correct
11 Correct 396 ms 416364 KB Output is correct
12 Correct 412 ms 424808 KB Output is correct
13 Correct 398 ms 423144 KB Output is correct
14 Correct 407 ms 425344 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 161528 KB Output is correct
2 Correct 876 ms 796792 KB Output is correct
3 Correct 877 ms 796792 KB Output is correct
4 Correct 965 ms 796792 KB Output is correct
5 Execution timed out 2145 ms 795756 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 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 13 ms 9856 KB Output is correct
11 Correct 13 ms 9856 KB Output is correct
12 Correct 14 ms 9856 KB Output is correct
13 Execution timed out 2047 ms 68960 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 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 Execution timed out 2098 ms 183016 KB Time limit exceeded
11 Halted 0 ms 0 KB -