oj.uz

Submission #705628

# Submission time Handle Problem Language Result Execution time Memory
705628 2023-03-04T20:10:38 Z Deepesson Burza (COCI16_burza) C++17
112 / 160
 115 ms 7232 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5688 KB Output is correct
2 Correct 113 ms 7232 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 88 ms 6860 KB Output is correct
6 Correct 20 ms 1748 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 6884 KB Output is correct
2 Correct 98 ms 6868 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 91 ms 6976 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6956 KB Output is correct
2 Correct 108 ms 6948 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 76 ms 5708 KB Output is correct
6 Correct 21 ms 1984 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 6748 KB Output is correct
2 Correct 97 ms 7136 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 67 ms 4884 KB Output is correct
6 Correct 21 ms 1620 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 6648 KB Output is correct
2 Correct 92 ms 6844 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 89 ms 6976 KB Output is correct
6 Correct 65 ms 4960 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 7116 KB Output is correct
2 Correct 90 ms 6764 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 75 ms 6336 KB Output is correct
6 Correct 53 ms 4308 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 7000 KB Output is correct
2 Correct 93 ms 6788 KB Output is correct
3 Correct 1 ms 244 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 88 ms 6848 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 6160 KB Output is correct
2 Correct 94 ms 7084 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 51 ms 4448 KB Output is correct
6 Correct 89 ms 7056 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5076 KB Output is correct
2 Correct 101 ms 7072 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 57 ms 4308 KB Output is correct
6 Correct 89 ms 6552 KB Output is correct

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5936 KB Output is correct
2 Correct 95 ms 6996 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Incorrect 81 ms 6036 KB Output isn't correct
6 Halted 0 ms 0 KB -