oj.uz

Submission #705685

# Submission time Handle Problem Language Result Execution time Memory
705685 2023-03-05T00:36:35 Z Deepesson Burza (COCI16_burza) C++17
160 / 160
 11 ms 1680 KB 
#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>=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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 11 ms 1620 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1620 KB Output is correct
2 Correct 11 ms 1620 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 11 ms 1680 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1620 KB Output is correct
2 Correct 11 ms 1620 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 11 ms 1620 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1620 KB Output is correct
2 Correct 11 ms 1620 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1620 KB Output is correct
2 Correct 11 ms 1620 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1564 KB Output is correct
2 Correct 10 ms 1648 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 11 ms 1620 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 11 ms 1620 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 11 ms 1672 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 11 ms 1672 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 1 ms 340 KB Output is correct