## 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(i, 1, k)
{
for (auto u : v[i])
{
if (tin[u] > cur+1) continue;
}
}
}
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