Submission #1010899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010899		WhiteZeros	Burza (COCI16_burza)	C++17	0 / 160	11 ms	860 KiB

burza

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define task "coci1617_r2_burza"
const int N = 4e2 + 1 , M = 20 , inf = 1e9 ; 
int n , k , stt = 0; 
vector<int> D[N] , depth[M] , cover[N];   
int dp[1 << M] , tin[N] , tout[N] , pos[N];
void maximize(int &a , int b){
    if(a < b) a = b ; 
}
void minimize(int &a , int b){
    if(a > b) a = b ; 
}
void dfs(int u , int p , int h){
    depth[h].push_back(u) ;
    if(h == k){
        pos[u] = ++stt ;  
        cover[u] = {u}; 
        return ; 
    }
    for(int v : D[u]){
        if(v == p) continue;    
        dfs(v , u , h + 1); 
        cover[u].insert(cover[u].end() , cover[v].begin() , cover[v].end()) ; 
    }
}
int main()
{
    ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
    if(ifstream(task".INP")){
        freopen(task".INP","r",stdin) ; 
        freopen(task".OUT","w",stdout) ;
    }
    cin >> n >> k ;
    if(k * k >= n){
        cout <<"DA" ; 
        return 0; 
    }
    for(int i = 1 ; i <= n ; i++) tin[i] = inf ; 
    for(int i = 1 ; i < n ; i++){
        int u , v ; 
        cin >> u >> v ; 
        D[u].push_back(v) ;
        D[v].push_back(u) ; 
    }
    dfs(1 , 0 , 0) ; 
    for(int i = 1 ; i <= n ; i++){
        if(cover[i].empty()) tin[i] = tout[i] = -1 ; 
        else {
            tin[i] = pos[cover[i].front()] ;  
            tout[i] = pos[cover[i].back()] ; 
        }
    }
    dp[0] = 0 ; 
    for(int i = 1 ; i < (1 << k) ; i++){
        for(int j = 0 ; j < k ; j++)
            if(i >> j & 1)
                for(const int &v : D[j + 1])
                    {
                        int pre = dp[i & ~(1 << j)] ; 
                        if(pre + 1>= tin[v]) maximize(dp[i] , tout[v]) ; 
                    }
        if(dp[i] == stt){
            cout <<"DA\n" ; 
            return 0 ; 
        }
    }
    cout <<"NE\n" ; 
    return 0;
}

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(task".INP","r",stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
burza.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen(task".OUT","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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