| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 537401 | mmonteiro | Burza (COCI16_burza) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
/*
* Author: Matheus Monteiro
*/
using namespace std;
#ifdef DEBUGMONTEIRO
#define _ << " , " <<
#define bug(x) cout << #x << " >>>>>>> " << x << endl;
#else
#define bug(x)
#endif
// #define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vii vector<ii>
#define LSOne(S) ((S) & (-S))
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int MAX = 800; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9; //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, k;
vector<int> G[MAX];
int tin[MAX], tout[MAX], level[MAX], timer;
vector<int> bucket[MAX];
int dp[1 << 21][MAX];
void dfs(int v, int p) {
if(level[v] >= 0)
bucket[level[v]].push_back(v);
tin[v] = timer + 1;
for(int u : G[v]) {
if(u != p) {
level[u] = level[v] + 1;
if(level[u] < k) {
dfs(u, v);
}
}
}
if(level[v] == k - 1)
timer++;
tout[v] = timer;
}
void solve() {
cin >> n >> k;
for(int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v; --u; --v;
G[u].push_back(v);
G[v].push_back(u);
}
level[0] = -1;
dfs(0, -1);
for(int i = 0; i <= k; ++i)
sort(bucket[i].begin(), bucket[i].end(), [&](int a, int b)
{
return tin[a] < tin[b];
}
);
for(int i = 0; i < (1 << k); ++i)
dp[i][0] = 1;
for(int i = 1; i < (1 << k); ++i)
for(int j = 0; j < k; ++j)
if(i & (1 << j))
for(int u : bucket[j])
if(dp[i ^ (1 << j)][ tin[u] - 1])
dp[i][ tout[u] ] = 1;
bool flag = false;
for(int i = 0; i < (1 << k); ++i)
if(dp[i][timer])
flag = true;
cout << (flag ? "DA\n" : "NE\n");
}
int32_t main() {
fastio;
int t = 1;
//cin >> t;
for(int caso = 1; caso <= t; ++caso) {
//cout << "Case #" << caso << ": ";
solve();
}
return 0;
}
/*
Before submit:
Check the corners cases
Check solution restrictions
For implementation solutions:
Check the flow of the variables
For intervals problems:
Think about two pointers
For complete search:
Think about cuts
If you get WA:
Reread your code looking for stupid typos
Try various manual testcases
Recheck the correctness of your algorithm
Reread the statement
Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
Change the coder (if you're with a team)
Give up. You may have other tasks to solve.
*/