oj.uz

Submission #242317

# Submission time Handle Problem Language Result Execution time Memory
242317 2020-06-27T08:45:59 Z dwsc Magic Tree (CEOI19_magictree) C++14
37 / 100
 2000 ms 796804 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];
    if (weight[u] != 0)return memo[u][j] = max(s,dp(u,j-1));
    else return memo[u][j] = s;
}
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 || m <= 1000){
    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);
    }
    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:21:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
magictree.cpp: In function 'int main()':
magictree.cpp:45:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < temp.size(); j++){
                         ~~^~~~~~~~~~~~~

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 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 45 ms 6392 KB Output is correct
2 Correct 36 ms 6524 KB Output is correct
3 Correct 73 ms 6380 KB Output is correct
4 Correct 75 ms 6640 KB Output is correct
5 Correct 72 ms 6508 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9856 KB Output is correct
2 Correct 13 ms 9984 KB Output is correct
3 Correct 13 ms 9856 KB Output is correct
4 Incorrect 61 ms 8276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 410204 KB Output is correct
2 Correct 246 ms 408592 KB Output is correct
3 Correct 261 ms 412648 KB Output is correct
4 Correct 230 ms 408932 KB Output is correct
5 Correct 248 ms 416156 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 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 338 ms 424176 KB Output is correct
11 Correct 293 ms 416368 KB Output is correct
12 Correct 270 ms 426728 KB Output is correct
13 Correct 288 ms 423148 KB Output is correct
14 Correct 290 ms 430064 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 161656 KB Output is correct
2 Execution timed out 2147 ms 796804 KB Time limit exceeded
3 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 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 9984 KB Output is correct
12 Correct 13 ms 9856 KB Output is correct
13 Incorrect 61 ms 8276 KB Output isn't correct
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 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 45 ms 6392 KB Output is correct
11 Correct 36 ms 6524 KB Output is correct
12 Correct 73 ms 6380 KB Output is correct
13 Correct 75 ms 6640 KB Output is correct
14 Correct 72 ms 6508 KB Output is correct
15 Correct 13 ms 9856 KB Output is correct
16 Correct 13 ms 9984 KB Output is correct
17 Correct 13 ms 9856 KB Output is correct
18 Incorrect 61 ms 8276 KB Output isn't correct
19 Halted 0 ms 0 KB -