oj.uz

답안 #371555

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
371555 2021-02-26T21:35:45 Z jainbot27 Burza (COCI16_burza) C++17
0 / 160
 631 ms 4204 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 401;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

void no(){
    cout << "DA\n"; exit(0);
}

int n, k;
vi adj[mxN];
int d[mxN], st[mxN], en[mxN];
int CNT=0;
int vis[mxN];
bool dp[401][1<<20];
vi node[mxN];;

void dfs(int u, int p){
    vis[u]=1;
    if(d[u]==k-1){
        st[u]=CNT++;
        en[u]=CNT;
        return;
    }  
    st[u]=CNT;
    trav(v, adj[u]){
        if(v==p) continue;
        d[v] = d[u]+1;
        dfs(v, u);
    }
    en[u]=CNT;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    if(k*k>n) {
        no();
    }
    F0R(i, n-1){
        int x, y; cin >> x >> y; x--; y--;
        adj[x].pb(y); adj[y].pb(x);
    }
    d[0]=-1;
    dfs(0, -1);
    FOR(i, 1, n) if(vis[i]) node[st[i]].pb(i);
    dp[0][0]=1;
    F0R(i, CNT){
        trav(v, node[i]){
            F0R(msk, 1<<k){
                if(!dp[i][msk]) continue;
                FOR(j, d[v], k){
                    if((msk&(1<<j))==0){
                        dp[en[v]][msk|(1<<j)]|=dp[i][msk];
                    }
                }
            }
        }    
    }
    int ans =0 ;
    F0R(msk, 1<<k){
        if(dp[CNT][msk]){
            ans=1;
        }
    }
    cout << (ans?"DA":"NE")<<nl;
    return 0;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 1004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 631 ms 3692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 578 ms 3916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 1804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 496 ms 3724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 610 ms 3796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 537 ms 4204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 138 ms 1516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 1132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 235 ms 2028 KB Output isn't correct
2 Halted 0 ms 0 KB -