oj.uz

Submission #1023865

# Submission time Handle Problem Language Result Execution time Memory
1023865 2024-07-15T08:04:56 Z caterpillow Burza (COCI16_burza) C++17
0 / 160
 342 ms 508536 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++;
    if (depth[u] == k) val[u] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
        val[u] += val[v];
    }
    jump[u] = t;
}

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));

    dbg(depth);
    dbg(pos);
    dbg(jump);
    dbg(val);
    dbg(rpos);

    // sanity check
    int cnt = 0;
    F0R (i, n) if (depth[i] == k) cnt++;
    if (cnt != val[0]) while (1);
    

    int ans = dp(0, 1, k);
    assert(ans <= val[0]);
    if (ans == val[0]) cout << "DA\n";
    else cout << "NE\n";
}

Compilation message

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

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 328 ms 508508 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 327 ms 508496 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 327 ms 508496 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 320 ms 508380 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 324 ms 508532 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 304 ms 508536 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 310 ms 508496 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 300 ms 508400 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 321 ms 508500 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 342 ms 508500 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -