| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 446627 |
2021-07-22T20:30:43 Z |
Deepesson |
Burza (COCI16_burza) |
C++17 |
|
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){
| ~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
55236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1078 ms |
111960 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
104784 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
110416 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1098 ms |
113180 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
163 ms |
103168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
698 ms |
111496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
