oj.uz

Submission #242302

# Submission time Handle Problem Language Result Execution time Memory
242302 2020-06-27T08:34:42 Z dwsc Magic Tree (CEOI19_magictree) C++14
6 / 100
 2000 ms 796748 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;
    int isline = 1;
    for (int i = 2; i <= n; i++){
        int p;
        cin >> p;
        adj[p].push_back(i);
        if (p != i-1) isline = 0;
    }
    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);
    }
    if (isline){
        vector<int> lis;
        for (int i= 1; i <= n; i++){
            int pos = upper_bound(lis.begin(),lis.end(),-ripe[i])-lis.begin();
            if (pos == lis.size()) lis.push_back(-ripe[i]);
            else lis[pos] = -ripe[i];
        }
        cout << lis.size();
        return 0;
    }
    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:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (pos == lis.size()) lis.push_back(-ripe[i]);
                 ~~~~^~~~~~~~~~~~~
magictree.cpp:53:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < temp.size(); j++){
                         ~~^~~~~~~~~~~~~
magictree.cpp:54: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 7 ms 2944 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 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 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 2100 ms 183736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 410092 KB Output is correct
2 Correct 432 ms 408612 KB Output is correct
3 Correct 421 ms 410728 KB Output is correct
4 Correct 400 ms 409096 KB Output is correct
5 Incorrect 169 ms 8940 KB Output isn't correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 7 ms 2944 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 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Correct 456 ms 424300 KB Output is correct
11 Correct 428 ms 416352 KB Output is correct
12 Correct 451 ms 425188 KB Output is correct
13 Correct 426 ms 423012 KB Output is correct
14 Incorrect 142 ms 8432 KB Output isn't correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 161528 KB Output is correct
2 Correct 947 ms 796684 KB Output is correct
3 Correct 916 ms 796748 KB Output is correct
4 Correct 1002 ms 796748 KB Output is correct
5 Execution timed out 2086 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 2944 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 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 6 ms 2816 KB Output is correct
10 Incorrect 7 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 7 ms 2944 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 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 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 2100 ms 183736 KB Time limit exceeded
11 Halted 0 ms 0 KB -