oj.uz

Submission #1050801

# Submission time Handle Problem Language Result Execution time Memory
1050801 2024-08-09T14:38:33 Z handlename Burza (COCI16_burza) C++17
160 / 160
 29 ms 1116 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
const int MOD=1e9+7;
// const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
long long power(long long a,long long b,long long p=MOD){
    long long res=1;
    while (b>0){
        if (b%2==1) res=(res*a)%p;
        b/=2;
        a=(a*a)%p;
    }
    return res;
}
int n,k,leafid;
vector<int> adj[401];
vector<int> nodesatdepth[22];
int pre[401],post[401];
void dfs(int x,int p,int dd){
    nodesatdepth[dd].pb(x);
    if (dd>=k){
        pre[x]=leafid;
        leafid++;
        post[x]=leafid;
        // if depth k+1 reached, stjepan has won
        return;
    }
    pre[x]=leafid;
    for (auto i:adj[x]){
        if (i==p) continue;
        dfs(i,x,dd+1);
    }
    post[x]=leafid;
}
int dp[1200001];
// dp[mask]=max number of leaves we can cover from the start
// given we take 1 node from each depth in mask
void runtc(){
    cin>>n>>k;
    for (int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    if (k*k>=n){
        cout<<"DA";
        return;
    }
    leafid=1;
    dfs(1,-1,0);
    for (int i=0;i<(1<<k);i++){
        for (int j=0;j<k;j++){ //depths
            if (!(i&(1<<j))) continue;
            for (auto u:nodesatdepth[j+1]){
                if (pre[u]<=dp[i^(1<<j)]+1){
                    dp[i]=max(dp[i],post[u]-1);
                }
            }
        }
        if (dp[i]==leafid-1){
            cout<<"DA";
            return;
        }
    }
    cout<<"NE";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("movie.in","r",stdin);
    // freopen("movie.out","w",stdout);
    // freopen("input1.in","r",stdin);
    // freopen("output1.out","w",stdout);
    //freopen("tower_rush_input.txt","r",stdin);
    //freopen("hackercup_output.txt","w",stdout);
    int tcs;
    // cin>>tcs;
    tcs=1;
    for (int i=1;i<=tcs;i++){
        // cout<<"Case #"<<i<<": ";
        runtc();
    }
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 23 ms 776 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 #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 928 KB Output is correct
2 Correct 23 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 29 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 860 KB Output is correct
2 Correct 23 ms 884 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 #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 860 KB Output is correct
2 Correct 23 ms 860 KB Output is correct
3 Correct 0 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 0 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 968 KB Output is correct
2 Correct 23 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 804 KB Output is correct
2 Correct 23 ms 980 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 23 ms 860 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 6 ms 604 KB Output is correct
2 Correct 23 ms 984 KB Output is correct
3 Correct 1 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 #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 23 ms 856 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 #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 588 KB Output is correct
2 Correct 23 ms 948 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 10 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct