이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
cout << (dp(0, 1, k) == val[0] ? "DA" : "NE") << endl;
}
컴파일 시 표준 에러 (stderr) 메시지
burza.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
97 | main() {
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |