oj.uz

Submission #440483

# Submission time Handle Problem Language Result Execution time Memory
440483 2021-07-02T10:17:40 Z Millad Burza (COCI16_burza) C++14
0 / 160
 1 ms 332 KB 
    // In the name of god
    #include <bits/stdc++.h>
     
    #define F first
    #define S second
    #define pb push_back
    #define all(x) x.begin(), x.end()
    #define Sort(x) sort(all(x))
    #define debug(x) cerr << #x << " : " << x << "\n"
    #define usefile freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
     
    using namespace std;
    typedef long long ll;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef string str;
     
    const ll maxn = 1e3 + 5;
    const ll mod = 1e9 + 7;
    const ll inf = 1e18;
    const ll sq = 500;
     
    ll n, k;
    bool dp[30][maxn];
    vector <ll> adj[maxn];
    void dfs(ll u, ll p){
     	dp[0][u] = 1;
            for(ll j : adj[u]){
                    if(j == p)continue;
                    dfs(j, u);
            }
            for(ll i = 1; i <= k; i ++){
                    ll cnt = 0;
                    for(ll j : adj[u]){
                            if(j == p)continue;
                            if(dp[i - 1][j]) cnt ++;
                    }
                    if(cnt > 1)dp[i][u] = 1;
            }
    }
    int main(){
            ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
            cin >> n >> k;
            if(k > 19)return cout << "NE", 0;
            for(ll i = 1; i < n; i ++){
                    ll u, v; cin >> u >> v;
                    adj[u].pb(v);
                    adj[v].pb(u);
            }
            dfs(1, 0);
            if(dp[k][1])cout << "DA";
            else cout << "NE";
    }

Subtask #1
0 / 16.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 16.0

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

Subtask #7
0 / 16.0

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

Subtask #8
0 / 16.0

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

Subtask #9
0 / 16.0

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

Subtask #10
0 / 16.0

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