oj.uz

Submission #914396

# Submission time Handle Problem Language Result Execution time Memory
914396 2024-01-21T23:19:23 Z phlap Burza (COCI16_burza) C++17
160 / 160
 44 ms 1556 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];
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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Output is correct
2 Correct 41 ms 1364 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1360 KB Output is correct
2 Correct 41 ms 1360 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 36 ms 1360 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1372 KB Output is correct
2 Correct 37 ms 1368 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 604 KB Output is correct
2 Correct 38 ms 1436 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1368 KB Output is correct
2 Correct 44 ms 1360 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1360 KB Output is correct
2 Correct 39 ms 1372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1364 KB Output is correct
2 Correct 39 ms 1492 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 38 ms 1384 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 600 KB Output is correct
2 Correct 39 ms 1372 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 496 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 608 KB Output is correct
2 Correct 40 ms 1556 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 856 KB Output is correct
2 Correct 39 ms 1496 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 17 ms 940 KB Output is correct
6 Correct 1 ms 348 KB Output is correct