제출 #1171288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171288		ayush_ag	Burza (COCI16_burza)	C++20	160 / 160	56 ms	1552 KiB

burza

#include <bits/stdc++.h>
using namespace std;
void fastio(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); 
}
int n,k;
void dfs(vector<vector<int>>& edges,vector<vector<int>>& cover,vector<vector<int>>& depth,vector<int>& mp,int leaf,int root,int d,int& cnt){
  if(d<=k)depth[d].push_back(leaf);
  if(d==k){
    mp[leaf]=cnt;cnt+=1;
    cover[leaf].push_back(mp[leaf]);
    return;
  }
  for(int i=0;i<edges[leaf].size();i++){
    if(edges[leaf][i]==root)continue;
    dfs(edges,cover,depth,mp,edges[leaf][i],leaf,d+1,cnt);
    for(int j=0;j<cover[edges[leaf][i]].size();j++){
      cover[leaf].push_back(cover[edges[leaf][i]][j]);
    }
  }
}

int32_t main() {
  cin>>n>>k;
  vector<vector<int>> edges(n);
  for(int i=0;i<n-1;i++){
    int a,b;cin>>a>>b;
    a-=1;b-=1;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  if(k>20){cout<<"DA\n";return 0;}
  vector<vector<int>> cover(n);
  vector<vector<int>> depth(k+1);
  vector<int> mp(n,0);
  int mx=1;
  dfs(edges,cover,depth,mp,0,-1,0,mx);
  //cout<<"dsf"<<"\n";
  vector<pair<int,int>> interval(n,{-1,-1});
  for(int i=0;i<n;i++){
    if(cover[i].size()==0)continue;
    interval[i]={cover[i][0],cover[i][cover[i].size()-1]};
  }
  // for(int i=0;i<n;i++){
  //   cout<<interval[i].first<<" "<<interval[i].second<<"\n";
  // }
  int upto=1<<(k+1);
  vector<int> ss(upto);
  ss[0]=0;mx-=1;
  //cout<<mx<<" "<<upto<<endl;
  for(int i=2;i<upto;i++){
    //cout<<i<<" dfs "<<endl;
    for(int j=1;j<=k;j++){
      if((i & (1<<j))==0)continue;
      int prev= ss[i ^ (1<<j)];
      //cout<<j<<endl;
      for(int l=0;l<depth[j].size();l++){
        //cout<<depth[j][l]<<" df ";
        if(interval[depth[j][l]].first<=prev+1)ss[i]=max(ss[i],interval[depth[j][l]].second);
      }
      //cout<<endl;
    }
    //cout<<ss[i]<<"\n";
    if(ss[i]==mx){cout<<"DA\n";return 0;}
  }
  cout<<"NE\n";
}

• 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