# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1052892 | coolsentenceidontremember | Burza (COCI16_burza) | C++17 | 26 ms | 1020 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>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define ld long double
#define ff first
#define ss second
#define db double
#define time_begin() auto begin = chrono::high_resolution_clock::now()
#define time_end() auto end = chrono::high_resolution_clock::now(); auto elapsed = chrono::duration_cast<chrono::nanoseconds>(end-begin); auto sec = elapsed.count() * 1e-9; cerr << "\n\nExecution time: " << sec << " seconds";
#define check_time() cerr << "\nStatus : "; if (sec>1) cerr << "Time Limit Exceeded 1!!!1!111"; else cerr << "You good brother"
#define precision(x) fixed << setprecision((x))
#define check_ok() cout << "it aight" << '\n'
using namespace std;
void setIO(string s = ""){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
if (!s.empty()){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
}
const int N = 400;
const int inf = 1000;
map<int, int> comp;
pair<int, int> segment[N+1];
vector<int> adj[N+1];
vector<int> depth[N+1];
int cnt = 0;
void dfs(int u, int p, int lvl, const int &max_lvl){
segment[u] = {inf, -inf};
depth[lvl].push_back(u);
if (lvl == max_lvl){
cnt++;
segment[u] = {u, u};
comp[u] = cnt;
return;
}
for (int v : adj[u]){
if (v != p) dfs(v, u, lvl+1, max_lvl);
segment[u].ff = min(segment[u].ff, segment[v].ff);
segment[u].ss = max(segment[u].ss, segment[v].ss);
}
return;
}
int main(){
int n, k;
cin >> n >> k;
for (int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if (k*k >= n){
cout << "DA";
return 0;
}
comp[inf] = inf;
comp[-inf] = -inf;
dfs(1, -1, 0, k);
for (int i = 1; i <= n; i++){
segment[i].ff = comp[segment[i].ff];
segment[i].ss = comp[segment[i].ss];
}
vector<int> dp(1<<k, 0);
for (int mask = 0; mask < (1<<k); mask++){
for (int b=0; b < k; b++){
if (mask & (1<<b)){
int prev = mask^(1<<b);
for (int u : depth[b+1]){
if (segment[u].ff <= prev+1) dp[mask] = max(dp[mask], max(prev, segment[u].ss));
}
}
}
if (dp[mask] == cnt){
cout << "DA";
return 0;
}
}
cout << "NE";
return 0;
}
Compilation message (stderr)
# | 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... |