Submission #778316

# Submission time Handle Problem Language Result Execution time Memory
778316 2023-07-10T08:29:42 Z RecursiveCo Magic Tree (CEOI19_magictree) C++14
22 / 100
1125 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<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], 1 + 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);
    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;
    }
    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:32:9: note: in expansion of macro 'forto'
   32 |         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:35:5: note: in expansion of macro 'forto'
   35 |     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:38:5: note: in expansion of macro 'forto'
   38 |     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:43:5: note: in expansion of macro 'get'
   43 |     get(n);
      |     ^~~
magictree.cpp:10:23: warning: unnecessary parentheses in declaration of 'm' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
magictree.cpp:44:5: note: in expansion of macro 'get'
   44 |     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:49:5: note: in expansion of macro 'forto'
   49 |     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:50:9: note: in expansion of macro 'get'
   50 |         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:55:5: note: in expansion of macro 'forto'
   55 |     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:56:9: note: in expansion of macro 'get'
   56 |         get(v);
      |         ^~~
magictree.cpp:10:23: warning: unnecessary parentheses in declaration of 'd' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
magictree.cpp:57:9: note: in expansion of macro 'get'
   57 |         get(d);
      |         ^~~
magictree.cpp:10:23: warning: unnecessary parentheses in declaration of 'w' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
magictree.cpp:58:9: note: in expansion of macro 'get'
   58 |         get(w);
      |         ^~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 1125 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 12 ms 16200 KB Output is correct
2 Correct 12 ms 16084 KB Output is correct
3 Correct 12 ms 16100 KB Output is correct
4 Runtime error 385 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 13312 KB Output isn't correct
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 212 KB Output is correct
3 Correct 1 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 86 ms 28140 KB Output is correct
11 Correct 66 ms 20376 KB Output is correct
12 Correct 96 ms 39120 KB Output is correct
13 Correct 41 ms 27936 KB Output is correct
14 Correct 62 ms 55732 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 306 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 212 KB Output is correct
3 Correct 1 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 12 ms 16200 KB Output is correct
11 Correct 12 ms 16084 KB Output is correct
12 Correct 12 ms 16100 KB Output is correct
13 Runtime error 385 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 212 KB Output is correct
3 Correct 1 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Runtime error 1125 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -