oj.uz

Submission #591435

# Submission time Handle Problem Language Result Execution time Memory
591435 2022-07-07T12:32:41 Z Mazaalai Burza (COCI16_burza) C++17
160 / 160
 9 ms 720 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
using namespace std;
using sint = short;
using VI = vector <sint>;
using PII = pair <sint, sint>;

const sint N = 401;
const sint K = 21;
const int M = 1<<20;

VI paths[N];
sint dp[M], reach[K][N];
sint n, m, k, leaf;
string yes = "DA";
string  no = "NE";
PII dfs(sint pos, sint par = -1, sint lvl = -1) {
    sint l = n, r = -n;
    if (lvl == k-1) {
        l = r = leaf++;
        chmax(reach[lvl][l], r);
        // cout << pos << "," << lvl << " " << l << " " << r << '\n';
        return {l, r};
    }
    for (auto& el : paths[pos]) {
        if (el == par) continue;
        PII tmp = dfs(el, pos, lvl+1);
        chmin(l, tmp.ff);
        chmax(r, tmp.ss);
    }
    if (r != -n) chmax(reach[lvl][l], r);
    // cout << pos << "," << lvl << " " << l << " " << r << '\n';
    return {l, r};
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("0.in", "r", stdin);
    // freopen("0.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        paths[a].pb(b);
        paths[b].pb(a);
    }
    if (k*k >= n) {
        cout << yes << "\n";
        return 0;
    }
    memset(reach, -1, sizeof(reach));
    dfs(1);
    for (sint i = 0; i < k; i++) 
    for (sint j = 1; j < leaf; j++) chmax(reach[i][j], reach[i][j-1]);
    for (int i = 1; i < (1<<k); i++) {
        for (sint j = 0; j < k; j++) {
            if (!(i&(1<<j)) || reach[j][dp[i^(1<<j)]]+1 <= dp[i]) continue;
            dp[i] = reach[j][dp[i^(1<<j)]]+1;
        }
        if (dp[i] == leaf) {
            cout << yes << '\n';
            return 0;
        }
    }
    cout << no << "\n";
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 616 KB Output is correct
3 Correct 0 ms 352 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 576 KB Output is correct
2 Correct 9 ms 504 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Correct 6 ms 596 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Correct 6 ms 720 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Correct 6 ms 596 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Correct 6 ms 608 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 6 ms 596 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 596 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 6 ms 552 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct