oj.uz

Submission #96744

# Submission time Handle Problem Language Result Execution time Memory
96744 2019-02-11T16:28:50 Z tieunhi Burza (COCI16_burza) C++14
160 / 160
 60 ms 1144 KB 
#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define pill pair<int, ll>
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define N 500
#define maxc 1000000007
#define mid (r + l)/2

using namespace std;

int n, k, dp[1 << 21], h[N], tt = 1, hmax[N], tin[N], tout[N], dd[N];
vector<int> a[N], v[N];

void stop() {cout <<"DA"; exit(0);}
bool bit(int x, int i) {return (x >> i) & 1;}
void inline MAX(int &A, int B) {A = max(A, B);}
void setup()
{
    cin >> n >> k;
    if (k >= 20) stop();

    FOR(i, 2, n)
    {
        int u, v; cin >> u >> v;
        a[u].PB(v);
        a[v].PB(u);
    }
}
void preDFS(int u, int p)
{
    hmax[u] = h[u];
    for (auto v : a[u])
    {
        if (v == p) continue;
        h[v] = h[u] + 1;
        preDFS(v, u);
        hmax[u] = max(hmax[u], hmax[v]);
    }
}
void DFS(int u, int p)
{
    tin[u] = tt;
    if (h[u] == k)
        tt++;
    for (auto v : a[u])
    {
        if (v == p || dd[v]) continue;
        DFS(v, u);
    }
    tout[u] = tt-1;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    //freopen("OUT.TXT", "w", stdout);
    setup();
    preDFS(1, -1);
    FOR(i, 1, n)
        if (h[i] > k || hmax[i] < k) dd[i] = 1;
        else v[h[i]].PB(i);
    if (hmax[1] < k) stop();
    DFS(1, -1);
    FOR(mask, 0, (1 << k)-1)
    {
        int cur = dp[mask];
        FOR(i, 1, k)
        {
            if (bit(mask, i-1)) continue;
            for (auto u : v[i])
            {
                if (tin[u] > cur+1) continue;
                MAX(dp[mask | (1 << (i-1))], max(dp[mask], tout[u]));
            }
        }
    }
    if (dp[(1 << k)-1] == tt-1) cout <<"DA";
    else cout <<"NE";
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Output is correct
2 Correct 55 ms 1016 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 888 KB Output is correct
2 Correct 56 ms 1144 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 60 ms 1016 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 948 KB Output is correct
2 Correct 53 ms 884 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 420 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 520 KB Output is correct
2 Correct 55 ms 860 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 952 KB Output is correct
2 Correct 57 ms 888 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 508 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 892 KB Output is correct
2 Correct 52 ms 984 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 888 KB Output is correct
2 Correct 54 ms 888 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 56 ms 880 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 504 KB Output is correct
2 Correct 56 ms 900 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 55 ms 888 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 636 KB Output is correct
2 Correct 56 ms 1016 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 26 ms 632 KB Output is correct
6 Correct 2 ms 376 KB Output is correct