Submission #705687

#	Time	Username	Problem	Language	Result	Execution time	Memory
705687		Deepesson	Burza (COCI16_burza)	C++17	160 / 160	12 ms	1680 KiB

burza

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define MAX 405
std::vector<int> con[MAX];
int N,K;
int pai[MAX],maxr[MAX];
std::vector<int> lista_especial;
int dfs(int pos,int prev,int dist){
    pai[pos]=prev;
    if(dist==K){
        lista_especial.push_back(pos);
        maxr[pos]=lista_especial.size()-1;
        return lista_especial.size()-1;
    }
    int best=0;
    for(auto&x:con[pos]){
        if(x==prev)continue;
        best=std::max(best,dfs(x,pos,dist+1));
    }
    maxr[pos]=best;
    return best;
}
int biggestr[1100000];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>K;
    if(K>=19){
        std::cout<<"DA\n";
        return 0;
    }
    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);
    }
    dfs(0,-1,0);
    std::vector<int> prof[K+1];
    for(int i=0;i!=(1<<K);++i){
        prof[__builtin_popcount(i)].push_back(i);
    }
    for(int i=K;i!=-1;--i){
        for(auto&x:prof[i]){
            int atual = biggestr[x];
            if(atual==lista_especial.size()){
                std::cout<<"DA\n";
                return 0;
            }
            int node = lista_especial[atual];
            for(int j=0;j!=K;++j){
                if(x&(1<<j)){
                    biggestr[x-(1<<j)]=std::max(biggestr[x-(1<<j)],maxr[node]+1);
                }
                node=pai[node];
            }
        }
    }
    std::cout<<"NE\n";
}

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if(atual==lista_especial.size()){
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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