Submission #705680

#TimeUsernameProblemLanguageResultExecution timeMemory
705680DeepessonBurza (COCI16_burza)C++17
160 / 160
14 ms1680 KiB
#include <bits/stdc++.h> #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>20){ 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:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             if(atual==lista_especial.size()){
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...