Submission #960773

#	Time	Username	Problem	Language	Result	Execution time	Memory
960773		doducanh	Burza (COCI16_burza)	C++14	0 / 160	35 ms	952 KiB

burza

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
int max_cover[(1<<20)+7];
vector<int>a[405];
vector<int>dep[405];
vector<vector<int>>cutoff;
vector<pair<int,int>>interval;
map<int,int>lost;
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()
{
    cin>>n>>k;
    cutoff.resize(n+1);
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        x--,y--;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    if(k*k>=n){
        cout<<"DA";
        return 0;
    }
    process(0,0,0);
    for(const vector<int>&cc:cutoff){
        if(cc.empty()){
            interval.push_back({-1,-1});
        }
        else interval.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 prev=max_cover[mask&(1<<to_add)];
                for(int v:dep[to_add+1]){
                    if(prev+1>=interval[v].fi){
                        curr=max(curr,interval[v].se);
                    }
                }
            }
        }
        if(curr==lost.size()){
            cout<<"DA";
            return 0;
        }
    }
    cout<<"NE";
}

Compilation message (stderr)

burza.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main()
      | ^~~~
burza.cpp: In function 'int main()':
burza.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         if(curr==lost.size()){
      |            ~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16