oj.uz

Submission #914395

# Submission time Handle Problem Language Result Execution time Memory
914395 2024-01-21T23:00:09 Z phlap Burza (COCI16_burza) C++17
0 / 160
 2 ms 860 KB 
#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];
int leafnum[401];
vector<int> atdepth[401];
int maxdepth[401];
int dp[1<<20];
int c=0;
int x, y;

void prune(int a, int b, int c){
  maxdepth[a]=c;
  for(auto i: adj[a]){
    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){
    leafnum[a]=++c;
    cover[a]={leafnum[a], leafnum[a]};
  }
}

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]==c) 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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -