oj.uz

Submission #242306

# Submission time Handle Problem Language Result Execution time Memory
242306 2020-06-27T08:38:33 Z dwsc Magic Tree (CEOI19_magictree) C++14
34 / 100
 2000 ms 796920 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";
    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:43:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < temp.size(); j++){
                         ~~^~~~~~~~~~~~~
magictree.cpp:44: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 2097 ms 189168 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 12 ms 9856 KB Output is correct
4 Execution timed out 2091 ms 73728 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 410092 KB Output is correct
2 Correct 309 ms 408576 KB Output is correct
3 Correct 303 ms 410732 KB Output is correct
4 Correct 292 ms 408944 KB Output is correct
5 Correct 326 ms 411368 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 335 ms 424176 KB Output is correct
11 Correct 338 ms 416368 KB Output is correct
12 Correct 320 ms 424808 KB Output is correct
13 Correct 339 ms 423052 KB Output is correct
14 Correct 320 ms 425320 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 161528 KB Output is correct
2 Correct 830 ms 796896 KB Output is correct
3 Correct 857 ms 796792 KB Output is correct
4 Correct 926 ms 796920 KB Output is correct
5 Execution timed out 2099 ms 796144 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 12 ms 9856 KB Output is correct
13 Execution timed out 2091 ms 73728 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 2097 ms 189168 KB Time limit exceeded
11 Halted 0 ms 0 KB -