oj.uz

Submission #1067278

# Submission time Handle Problem Language Result Execution time Memory
1067278 2024-08-20T13:54:52 Z KawakiMeido Burza (COCI16_burza) C++17
0 / 160
 46 ms 2696 KB 
/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 400;
const int INF = 1e9+7;
const long long LLINF = 1e18+3;

/*TestCases*/
int test=1;
void solve();
void TestCases(bool v){
    if (v) cin >> test;
    while(test--) solve();
}

/*Global Variables*/
int n,k,leafcnt=0,timedfs=-1;
int in[N],out[N];
int depth[N];
int t[N];
vector<int> a[N];
int dp[(1<<20)+10];

bool DFSbuild(int u, int p, int d){
    if (d==0){
        ++timedfs;
        t[u] = timedfs;
        in[timedfs] = out[timedfs] = ++leafcnt;
        depth[timedfs] = d;
        return true;
    }

    int ver = false;

    int tmpin = INF, tmpout=0;
    for (auto v:a[u]){
        if (v==p) continue;
        bool tmp = DFSbuild(v,u,d-1);
        ver = (ver||tmp);
        tmpin = min(tmpin,in[t[v]]);
        tmpout = max(tmpout,out[t[v]]);
    }
    if (ver){
        ++timedfs;
        t[u] = timedfs;
        if (tmpin == INF) in[timedfs] = 0;
        else in[timedfs] = tmpin;
        out[timedfs] = tmpout;
        depth[timedfs] = d;
    }
    return ver;
}

/*Solution*/
void solve(){
    cin >> n >> k;
    for (int i=1; i<n; i++){
        int u,v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    if (k*k>n){
        cout << "DA" << endl;
        return;
    }
    DFSbuild(1,0,k);
    for (int i=1; i<=n; i++){

    }
    if (leafcnt == 0){
        cout << "DA" << endl;
        return;
    }

    for (int mask=1; mask<(1<<k); mask++){
        dp[mask] = -1;
    }

//    for (int i=1; i<=n; i++){
//        cout << t[i] << endl;
//    }

    for (int i=0; i<timedfs; i++){
        int idx = depth[i];
        for (int mask=0; mask<(1<<k); mask++){
            if (mask&(1<<idx)){
                int pre = mask^(1<<idx);
                if (dp[pre]>=in[i]-1){
                    dp[mask] = max(dp[pre],out[i]);
                }
            }
        }
    }
    if (dp[(1<<k)-1]>=leafcnt){
        cout << "DA" << endl;
    }
    else cout << "NE" << endl;
}

/*Driver Code*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    TestCases(0);

    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 2696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2696 KB Output isn't correct
2 Halted 0 ms 0 KB -