Submission #960759

#TimeUsernameProblemLanguageResultExecution timeMemory
960759doducanhBurza (COCI16_burza)C++14
160 / 160
37 ms1536 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second vector<int>a[405]; map<int,int>lost; int max_cover[1<<20+7]; vector<vector<int>>cutoff; vector<pair<int,int>>intervals; vector<int>dep[405]; int n,k; void process(int at,int prev,int depth) { dep[depth].push_back(at); if(depth==k){ lost[at]=lost.size(); cutoff[at]={at}; return; } for(int v:a[at])if(v!=prev){ process(v,at,depth+1); cutoff[at].insert(cutoff[at].end(),cutoff[v].begin(),cutoff[v].end()); } } main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n>>k; cutoff.resize(n+1); for(int i=1;i<n;i++){ int x,y; cin>>x>>y; x--; y--; a[x].push_back(y); a[y].push_back(x); } if(k*k>=n)return cout<<"DA",0; process(0,0,0); for(const vector<int>&cc:cutoff){ if(cc.empty()){ intervals.push_back({-1,-1}); } else intervals.push_back({lost[cc.front()]+1,lost[cc.back()]+1}); } max_cover[0]=0; for(int mask=1;mask<(1<<k);mask++){ int &curr=max_cover[mask]; for(int to_add=0;to_add<k;to_add++){ if(((mask>>(to_add))&1)){ int pre=max_cover[mask^(1<<to_add)]; for(int v:dep[to_add+1]){ if(intervals[v].fi<=pre+1){ curr=max(curr,intervals[v].se); } } } } if(max_cover[mask]==lost.size()){ cout<<"DA"; return 0; } } cout<<"NE"; return 0; }

Compilation message (stderr)

burza.cpp:9:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    9 | int max_cover[1<<20+7];
      |                  ~~^~
burza.cpp:27:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main()
      | ^~~~
burza.cpp: In function 'int main()':
burza.cpp:61:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if(max_cover[mask]==lost.size()){
      |            ~~~~~~~~~~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...