제출 #446627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446627		Deepesson	Burza (COCI16_burza)	C++17	0 / 160	1099 ms	113240 KiB

burza

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 1050000
#define NODES 500
std::vector<int> con[NODES];
bool existe[MAX][22];
int tab[MAX][22];
int camadas[NODES];
int N,K;
typedef std::pair<int,int> pii;
int prof[NODES];
int dfs(int pos,int prev){
    int max = 1;
    for(auto&x:con[pos]) {
        if(x==prev)continue;
        max=std::max(max,1+dfs(x,pos));
    }
    return prof[pos]=max;
}
int expulso[NODES];
std::vector<pii> noscamada[22];
int indices_valores[NODES];
int pentes[NODES];
int dp(int pente,int pos){
    //printf("%d %d\n",pente,pos);
    if(!pente)return pos-1;
    if(existe[pente][pos])return tab[pente][pos];
    existe[pente][pos]=true;
    int prox=0;
    int req=0;
    for(int i = 0;i!=21;++i){
        if(pente&(1<<i)){
            if((prox&(pentes[noscamada[pos][i].second]))!=0){
                printf("WTF\n");
            }
            prox|=pentes[noscamada[pos][i].second];
            req=std::max(req,pos+expulso[noscamada[pos][i].first]);
        }
    }
   // printf("Pente: %d\n",prox);
  // if(pos==16)printf("Req:%d <%d>\n",req,prox);
    if(!prox)return std::max(req,pos);
    int min = 1e6;
    for(int i=0;i!=21;++i){
        if(prox&(1<<i)){
            min=std::min(min,dp(prox-(1<<i),pos+1));
        }
    }
    return tab[pente][pos]=std::max(req,min);
}
int main()
{
    for(auto&x:indices_valores)x=-1;
    std::cin>>N>>K;
    if(K>=20){printf("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);
    }
    std::queue<pii> queue;
    queue.push({0,0});
    bool visitou[NODES]={};
    while(queue.size()){
        auto _ = queue.front();
        queue.pop();
        auto pos = _.first;
        auto custo = _.second;
        if(visitou[pos])continue;
        visitou[pos]=true;
        camadas[pos]=custo;
        for(auto&x:con[pos]){
            queue.push({x,custo+1});
        }
    }
    dfs(0,-1);
    for(int i=0;i!=N;++i){
        //printf("Camada %d %d\n",camadas[i],i);
        if(camadas[i]<20){
            noscamada[camadas[i]].push_back({prof[i],i});
        }
    }
    int minimum=0;
    for(int i=0;i!=20;++i){
        std::sort(noscamada[i].begin(),noscamada[i].end(),std::greater<pii>());
        while(noscamada[i].size()>20){
      //      printf("F %d %d %d\n",i,noscamada[i].back().first,noscamada[i].back().second);
            minimum=std::max(minimum,noscamada[i].back().first);
            expulso[noscamada[i].back().second]=1+noscamada[i].back().first;
        //    printf("-->%d\n",expulso[noscamada[i].back().second]);
            noscamada[i].pop_back();
        }
        for(int j=0;j!=noscamada[i].size();++j){
            indices_valores[noscamada[i][j].second]=j;
        }
   //     std::cout<<"Size:"<<i<<" "<<noscamada[i].size()<<"\n";
    }
    for(int i=0;i!=N;++i){
       if(indices_valores[i]==-1)continue;
       for(auto&x:con[i]){
            if(camadas[x]!=camadas[i]+1)continue;
            if(indices_valores[x]!=-1){
                pentes[i]|=(1<<indices_valores[x]);
            }else {expulso[i]=std::max(expulso[i],1+expulso[x]);/*printf("Atualiza %d\n",expulso[i]);*/}
       }

    }
    int val = dp(1,0);
   // std::cout << val << "\n";
    if(val<K){
        printf("DA\n");
    }else printf("NE\n");
}

컴파일 시 표준 에러 (stderr) 메시지

burza.cpp: In function 'int main()':
burza.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int j=0;j!=noscamada[i].size();++j){
      |                     ~^~~~~~~~~~~~~~~~~~~~~

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