oj.uz

Submission #1023853

# Submission time Handle Problem Language Result Execution time Memory
1023853 2024-07-15T07:53:03 Z caterpillow Burza (COCI16_burza) C++17
0 / 160
 145 ms 250992 KB 
#include <bits/stdc++.h>
#include <random>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

you want to stop the coin from taking a path of length k
you only block off nodes at the same depth as the turn number
    ie you block off one of the immediate subtrees
hence, you block off one node at depths 1, 2, 3, ... k

take dfs order

let dp[i][j][k] be the max # of depth k nodes u can block off 
    in i's subtree using depths only in the range [j, k]

    if you take the current node (and its allowed) you split the range and take the sum of the dps in its next sibling (or next node, if non exists)
    otherwise, you go into the next node

*/

int n, k, t;
vt<vt<int>> adj;
vt<int> depth, pos, jump, val, rpos;

void dfs(int u, int p = -1) {
    pos[u] = t++;
    int last = -1;
    if (depth[u] == k) val[u] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
        if (last != -1) jump[last] = pos[v];
        last = v;
        val[u] += val[v];
    }
    if (last != -1) jump[last] = pos[last] + 1;
}

int memo[400][400][400];

int dp(int i, int l, int r) {
    if (i == n) return 0;
    if (l > r) return 0;
    if (memo[i][l][r] != -1) return memo[i][l][r];
    int u = rpos[i]; // get the actual node index at this position

    int ans = 0;
    if (l <= depth[i] && depth[i] <= r) { // allowed to take yourself
        ans = val[u] + dp(jump[u], l, depth[u] - 1) + dp(jump[u], depth[u] + 1, r);
    }
    ans = max(ans, dp(i + 1, l, r));

    return memo[i][l][r] = ans;
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> k;
    adj.resize(n);
    depth = pos = jump = val = rpos = vt<int>(n, 0);
    F0R (i, n - 1) {
        int u, v; cin >> u >> v;
        u--, v--;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(0);
    F0R (i, n) rpos[pos[i]] = i;
    memset(memo, -1, sizeof(memo));

    cout << (dp(0, 1, k) == val[0] ? "DA" : "NE") << endl;
}

Compilation message

burza.cpp:100:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main() {
      | ^~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 250908 KB Output is correct
2 Correct 114 ms 250960 KB Output is correct
3 Incorrect 122 ms 250992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 250976 KB Output is correct
2 Correct 119 ms 250964 KB Output is correct
3 Incorrect 124 ms 250764 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 250744 KB Output is correct
2 Correct 121 ms 250900 KB Output is correct
3 Incorrect 122 ms 250964 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 250856 KB Output is correct
2 Correct 132 ms 250960 KB Output is correct
3 Incorrect 125 ms 250780 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 250960 KB Output is correct
2 Correct 122 ms 250964 KB Output is correct
3 Incorrect 117 ms 250812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 250936 KB Output is correct
2 Correct 124 ms 250960 KB Output is correct
3 Incorrect 145 ms 250972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 250964 KB Output is correct
2 Correct 116 ms 250788 KB Output is correct
3 Incorrect 123 ms 250852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 250960 KB Output is correct
2 Correct 141 ms 250760 KB Output is correct
3 Incorrect 123 ms 250964 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 250852 KB Output is correct
2 Correct 122 ms 250860 KB Output is correct
3 Incorrect 129 ms 250884 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 250964 KB Output is correct
2 Correct 133 ms 250844 KB Output is correct
3 Incorrect 141 ms 250832 KB Output isn't correct
4 Halted 0 ms 0 KB -