제출 #1023870

#제출 시각아이디문제언어결과실행 시간메모리
1023870caterpillowBurza (COCI16_burza)C++17
0 / 160
143 ms251212 KiB
#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 int n, k, t; vt<vt<int>> adj; vt<int> depth, pos, jump, val, rpos; vt<int> sfx; 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); } if (depth[u] < k) 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)); int ans = dp(0, 1, k); if (ans == val[0]) cout << "DA\n"; else cout << "NE\n"; }

컴파일 시 표준 에러 (stderr) 메시지

burza.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...