Submission #778364

# Submission time Handle Problem Language Result Execution time Memory
778364 2023-07-10T08:54:59 Z RecursiveCo Magic Tree (CEOI19_magictree) C++14
34 / 100
608 ms 1048576 KB
// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

#define int long long int

vector<vector<int>> adjList;
vector<bool> visited;
vector<int> pos;
vector<int> W;
vector<vector<int>> dp;
int k;

void dfs(int v) {
    visited[v] = true;
    vector<int> cur(k, 0);
    int sum = 0;
    for (int con: adjList[v]) {
        if (!visited[con]) dfs(con);
        forto(k, i) cur[i] += dp[con][i];
        if (pos[v] != 1e18) sum += dp[con][pos[v]];
    }
    forto(k, i) {
        if (i >= pos[v]) cur[i] = max(cur[i], W[v] + sum);
    }
    forto(k, i) dp[v][i] = cur[i];
}

signed main() {
    improvePerformance;
    get(n);
    get(m);
    cin >> k;
    adjList.resize(n);
    visited.resize(n, false);
    pos.resize(n, 1e18);
    W.resize(n, -1);
    forto(n - 1, i) {
        get(cur);
        cur--;
        adjList[i + 1].push_back(cur);
        adjList[cur].push_back(i + 1);
    }
    forto(m, i) {
        get(v);
        get(d);
        get(w);
        v--;
        d--;
        pos[v] = d;
        W[v] = w;
    }
    dp.resize(n, vector<int>(k, 0));
    dfs(0);
    out(dp[0][k - 1]);
}

Compilation message

magictree.cpp: In function 'void dfs(long long int)':
magictree.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
magictree.cpp:33:9: note: in expansion of macro 'forto'
   33 |         forto(k, i) cur[i] += dp[con][i];
      |         ^~~~~
magictree.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
magictree.cpp:36:5: note: in expansion of macro 'forto'
   36 |     forto(k, i) {
      |     ^~~~~
magictree.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
magictree.cpp:39:5: note: in expansion of macro 'forto'
   39 |     forto(k, i) dp[v][i] = cur[i];
      |     ^~~~~
magictree.cpp: In function 'int main()':
magictree.cpp:10:23: warning: unnecessary parentheses in declaration of 'n' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
magictree.cpp:44:5: note: in expansion of macro 'get'
   44 |     get(n);
      |     ^~~
magictree.cpp:10:23: warning: unnecessary parentheses in declaration of 'm' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
magictree.cpp:45:5: note: in expansion of macro 'get'
   45 |     get(m);
      |     ^~~
magictree.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
magictree.cpp:51:5: note: in expansion of macro 'forto'
   51 |     forto(n - 1, i) {
      |     ^~~~~
magictree.cpp:10:23: warning: unnecessary parentheses in declaration of 'cur' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
magictree.cpp:52:9: note: in expansion of macro 'get'
   52 |         get(cur);
      |         ^~~
magictree.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
magictree.cpp:57:5: note: in expansion of macro 'forto'
   57 |     forto(m, i) {
      |     ^~~~~
magictree.cpp:10:23: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
magictree.cpp:58:9: note: in expansion of macro 'get'
   58 |         get(v);
      |         ^~~
magictree.cpp:10:23: warning: unnecessary parentheses in declaration of 'd' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
magictree.cpp:59:9: note: in expansion of macro 'get'
   59 |         get(d);
      |         ^~~
magictree.cpp:10:23: warning: unnecessary parentheses in declaration of 'w' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
magictree.cpp:60:9: note: in expansion of macro 'get'
   60 |         get(w);
      |         ^~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 608 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 12 ms 16212 KB Output is correct
2 Correct 12 ms 16212 KB Output is correct
3 Correct 12 ms 16196 KB Output is correct
4 Runtime error 379 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 54 ms 15580 KB Output is correct
2 Correct 70 ms 15580 KB Output is correct
3 Correct 56 ms 20832 KB Output is correct
4 Correct 36 ms 15276 KB Output is correct
5 Correct 54 ms 29040 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 91 ms 29032 KB Output is correct
11 Correct 76 ms 21156 KB Output is correct
12 Correct 81 ms 39852 KB Output is correct
13 Correct 56 ms 28748 KB Output is correct
14 Correct 62 ms 56516 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 322 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 12 ms 16212 KB Output is correct
11 Correct 12 ms 16212 KB Output is correct
12 Correct 12 ms 16196 KB Output is correct
13 Runtime error 379 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Runtime error 608 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -