oj.uz

Submission #395565

# Submission time Handle Problem Language Result Execution time Memory
395565 2021-04-28T14:21:41 Z iANikzad Burza (COCI16_burza) C++14
160 / 160
 84 ms 10564 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
//#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 4e2 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int maxl = 20;
const int SQ = 400;

int n, k;

int dp[maxn][(1 << maxl)];
vector<int> vec[maxn];

vector<int> adj[maxn];

int h[maxn];
int st[maxn], en[maxn];
int timer;

void dfs(int v,int par = 0)
{
    if(h[v] == k - 1)
    {
        st[v] = timer++; en[v] = timer;
        return;
    }

    st[v] = timer;
    for(int u : adj[v])
    {
        if(u == par) continue;
        h[u] = h[v] + 1;
        dfs(u, v);
    }
    en[v] = timer;
}

int32_t main()
{
    FAST;

    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(n <= k * k) return cout << "DA\n", 0;

    h[1] = -1;
    dfs(1);

    for(int i = 2; i <= n; i++)
        vec[st[i]].pb(i);

    dp[0][0] = 1;
    for(int i = 0; i < timer; i++)
        for(int mask = 0; mask < (1 << k); mask++) if(dp[i][mask])
            for(int v : vec[i]) if(!(mask >> h[v] & 1))
                dp[en[v]][mask + (1 << h[v])] = 1;

    for(int mask = 0; mask < (1 << k); mask++) if(dp[timer][mask]) return cout << "DA\n", 0;
    cout << "NE\n";

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1740 KB Output is correct
2 Correct 51 ms 7796 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 8564 KB Output is correct
2 Correct 56 ms 8000 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 77 ms 9320 KB Output is correct
6 Correct 1 ms 1612 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8900 KB Output is correct
2 Correct 58 ms 8028 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 588 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3020 KB Output is correct
2 Correct 73 ms 10564 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6848 KB Output is correct
2 Correct 63 ms 9284 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 1480 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8516 KB Output is correct
2 Correct 64 ms 8404 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9596 KB Output is correct
2 Correct 65 ms 8516 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 74 ms 9964 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2900 KB Output is correct
2 Correct 63 ms 8532 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1356 KB Output is correct
2 Correct 78 ms 9616 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 2 ms 1356 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4760 KB Output is correct
2 Correct 82 ms 9492 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 29 ms 4804 KB Output is correct
6 Correct 1 ms 844 KB Output is correct