Submission #705628

#	Time	Username	Problem	Language	Result	Execution time	Memory
705628		Deepesson	Burza (COCI16_burza)	C++17	112 / 160	115 ms	7232 KiB

burza

#include <bits/stdc++.h>
#define MAX 405
unsigned char tab[MAX][MAX][2048];
bool existe[MAX][MAX][2048];
int camadas[MAX];
std::vector<int> con[MAX];
int dp(int pos,int cur,int bits);
int atribuir(int pos,int sobra,int manda,int cur,int place){
    if(pos==9){
        return std::max(1+dp(con[place][cur],0,manda),dp(place,cur+1,sobra));
    }
    if(sobra&(1<<pos)){
        return std::min(atribuir(pos+1,sobra,manda,cur,place),atribuir(pos+1,sobra-(1<<pos),manda+(1<<pos),cur,place));
    }
    return atribuir(pos+1,sobra,manda,cur,place);
}
int dp(int pos,int cur,int bits) {
    if(existe[pos][cur][bits])return tab[pos][cur][bits];
    existe[pos][cur][bits]=true;
    if(cur==con[pos].size())return 0;
    //std::cout << pos << " " << cur << " " << bits << "\n";
    if(camadas[con[pos][cur]]<=camadas[pos])return tab[pos][cur][bits]=dp(pos,cur+1,bits);
    if(bits&(1<<camadas[pos])) {
        return tab[pos][cur][bits]=std::min(dp(pos,cur+1,bits-(1<<camadas[pos])),atribuir(0,bits,0,cur,pos));
    }
    return tab[pos][cur][bits]=atribuir(0,bits,0,cur,pos);
}
int main()
{
    int N,K;
    std::cin>>N>>K;
    for(int i=1;i!=N;++i) {
        int a,b;std::cin>>a>>b;
        --a;--b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
  if(K>20){
    printf("DA\n");
    return 0;
  }
    bool visitou[N]={};
    typedef std::pair<int,int> pii;
    std::queue<pii> queue;
    queue.push({0,0});
    while(queue.size()){
        auto _ = queue.front();
        queue.pop();
        auto custo = _.first;
        auto pos = _.second;
        if(visitou[pos])continue;
        visitou[pos]=true;
        camadas[pos]=custo;
        for(auto&x:con[pos]){
            queue.push({custo+1,x});
        }
    }
    int val = dp(0,0,2047);
 //   std::cout<<val<<"\n";
    if(val<K){
        printf("DA\n");
    }else printf("NE\n");
}

Compilation message (stderr)

burza.cpp: In function 'int dp(int, int, int)':
burza.cpp:20:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     if(cur==con[pos].size())return 0;
      |        ~~~^~~~~~~~~~~~~~~~~

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