Submission #914397

#	Time	Username	Problem	Language	Result	Execution time	Memory
914397		vjudge1	Burza (COCI16_burza)	C++17	160 / 160	52 ms	1548 KiB

burza

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M=1e9+7;

set<int> adj[401];
pair<int, int> cover[401];
vector<int> atdepth[401];
int maxdepth[401];
int dp[1<<20];
int leaves=0;
int x, y;

void prune(int a, int b, int c){
  maxdepth[a]=c;
  set<int> temp=adj[a];
  for(auto i: temp){
    if(i==b) continue;
    prune(i, a, c+1);
    maxdepth[a]=max(maxdepth[a], maxdepth[i]);
    if(maxdepth[i]<y) adj[a].erase(i);
  }
}

void dfs(int a, int b, int d){
  atdepth[d].push_back(a);
  cover[a]={LLONG_MAX/2, LLONG_MIN/2};
  bool flag=true;
  for(auto i: adj[a]){
    if(i==b) continue;
    flag=false;
    dfs(i, a, d+1);
    cover[a].first=min(cover[a].first, cover[i].first);
    cover[a].second=max(cover[a].second, cover[i].second);
  }
  if(flag) cover[a]={++leaves, leaves};
}

void solve(){
  cin>>x>>y;
  for(int i=0; i<x-1; i++){
    int a, b;
    cin>>a>>b;
    adj[a].insert(b);
    adj[b].insert(a);
  }
  if(y>=20){
    cout<<"DA";
    return;
  }
  prune(1, 0, 0);
  dfs(1, 0, 0);
  for(int i=0; i<(1<<y); i++){
    for(int j=0; j<y; j++){
      if(i&(1<<j)){
        dp[i]=max(dp[i], dp[i^(1<<j)]);
        for(auto k: atdepth[j+1]){
          if(cover[k].first<=dp[i^(1<<j)]+1) dp[i]=max(dp[i], cover[k].second);
        }
      }
    }
  }
  if(dp[(1<<y)-1]==leaves || adj[1].empty()) cout<<"DA";
  else cout<<"NE";
}

signed main(){
  //freopen("in", "r", stdin); //freopen("out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  int t=1; //cin>>t;
  while(t--) solve();
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16