# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1010900 | WhiteZeros | Burza (COCI16_burza) | C++17 | 34 ms | 996 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 <iostream>
#include<bits/stdc++.h>
using namespace std;
#define task "coci1617_r2_burza"
const int N = 4e2 + 1 , M = 20 , inf = 1e9 ;
int n , k , stt = 0;
vector<int> D[N] , depth[M] , cover[N];
int dp[1 << M] , tin[N] , tout[N] , pos[N];
void maximize(int &a , int b){
if(a < b) a = b ;
}
void minimize(int &a , int b){
if(a > b) a = b ;
}
void dfs(int u , int p , int h){
depth[h].push_back(u) ;
if(h == k){
pos[u] = ++stt ;
cover[u] = {u};
return ;
}
for(int v : D[u]){
if(v == p) continue;
dfs(v , u , h + 1);
cover[u].insert(cover[u].end() , cover[v].begin() , cover[v].end()) ;
}
}
int main()
{
ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
if(ifstream(task".INP")){
freopen(task".INP","r",stdin) ;
freopen(task".OUT","w",stdout) ;
}
cin >> n >> k ;
if(k * k >= n){
cout <<"DA" ;
return 0;
}
for(int i = 1 ; i <= n ; i++) tin[i] = inf ;
for(int i = 1 ; i < n ; i++){
int u , v ;
cin >> u >> v ;
D[u].push_back(v) ;
D[v].push_back(u) ;
}
dfs(1 , 0 , 0) ;
for(int i = 1 ; i <= n ; i++){
if(cover[i].empty()) tin[i] = tout[i] = -1 ;
else {
tin[i] = pos[cover[i].front()] ;
tout[i] = pos[cover[i].back()] ;
}
}
dp[0] = 0;
for (int ss = 1; ss < (1 << k); ss++) {
int &curr = dp[ss];
for (int to_add = 0; to_add < k; to_add++) {
if ((ss & (1 << to_add)) != 0) {
int prev = dp[ss & ~(1 << to_add)];
for (int n : depth[to_add + 1]) {
if (tin[n] <= prev + 1) {
curr = max(curr, tout[n]);
}
}
}
}
if (dp[ss] == stt) {
cout << "DA" << endl;
return 0;
}
}
cout << "NE" << endl;
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... |