oj.uz

Submission #1067303

# Submission time Handle Problem Language Result Execution time Memory
1067303 2024-08-20T14:23:13 Z KawakiMeido Burza (COCI16_burza) C++17
160 / 160
 54 ms 2904 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);
        if (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);
//    cout << leafcnt << endl;
    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++){
//        cout << in[i] << " " << out[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[mask] == leafcnt){
                cout << "DA" << endl;
                return;
            }
        }
    }
    cout << "NE" << endl;
}

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

    TestCases(0);

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Output is correct
2 Correct 49 ms 2700 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2652 KB Output is correct
2 Correct 49 ms 2652 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 46 ms 2652 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2652 KB Output is correct
2 Correct 50 ms 2652 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 604 KB Output is correct
2 Correct 50 ms 2700 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2652 KB Output is correct
2 Correct 48 ms 2652 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2652 KB Output is correct
2 Correct 53 ms 2648 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2652 KB Output is correct
2 Correct 47 ms 2652 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 45 ms 2648 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 604 KB Output is correct
2 Correct 49 ms 2904 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 548 KB Output is correct
2 Correct 49 ms 2652 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2652 KB Output is correct
2 Correct 54 ms 2648 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 20 ms 2728 KB Output is correct
6 Correct 0 ms 348 KB Output is correct