oj.uz

Submission #371561

# Submission time Handle Problem Language Result Execution time Memory
371561 2021-02-26T21:44:33 Z jainbot27 Burza (COCI16_burza) C++17
160 / 160
 95 ms 3328 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) node[st[i]].pb(i);
    //F0R(i, n) cout << d[i] << ' ';
    //cout << nl;
    dp[0][0]=1;
    F0R(i, CNT){
        trav(v, node[i]){
            F0R(msk, 1<<k){
                if(!dp[i][msk]) continue;
                if((msk&(1<<d[v]))==0){
                    dp[en[v]][msk|(1<<d[v])]|=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
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1004 KB Output is correct
2 Correct 71 ms 2796 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 492 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2796 KB Output is correct
2 Correct 69 ms 2796 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 86 ms 3052 KB Output is correct
6 Correct 2 ms 1152 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2900 KB Output is correct
2 Correct 84 ms 2668 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 492 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1388 KB Output is correct
2 Correct 85 ms 3328 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 492 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2324 KB Output is correct
2 Correct 75 ms 3052 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 1132 KB Output is correct
6 Correct 1 ms 876 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2796 KB Output is correct
2 Correct 86 ms 2924 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 876 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3128 KB Output is correct
2 Correct 79 ms 2944 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 95 ms 3180 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1260 KB Output is correct
2 Correct 75 ms 2796 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 1132 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 876 KB Output is correct
2 Correct 84 ms 3024 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1644 KB Output is correct
2 Correct 80 ms 3052 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 34 ms 1772 KB Output is correct
6 Correct 1 ms 768 KB Output is correct