답안 #96744 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96744	2019-02-11T16:28:50 Z	tieunhi	Burza (COCI16_burza)	C++14	160 / 160	60 ms	1144 KB

burza

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #96744

Compilation message