oj.uz

답안 #446627

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446627 2021-07-22T20:30:43 Z Deepesson Burza (COCI16_burza) C++17
0 / 160
 1000 ms 113240 KB 
#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");
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 96 ms 55236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1078 ms 111960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1079 ms 104784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 83712 KB Output is correct
2 Execution timed out 1099 ms 112956 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1075 ms 110416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 955 ms 109844 KB Output is correct
2 Execution timed out 1085 ms 113240 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1098 ms 113180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 482 ms 82792 KB Output is correct
2 Execution timed out 1059 ms 104368 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 163 ms 103168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 698 ms 111496 KB Output isn't correct
2 Halted 0 ms 0 KB -