oj.uz

Submission #150978

# Submission time Handle Problem Language Result Execution time Memory
150978 2019-09-01T13:41:15 Z letrongdat Burza (COCI16_burza) C++17
160 / 160
 16 ms 4984 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb                  push_back
#define repn(i, a, b)       for(int i=a; i<b; ++i)
const int N = 410;
const int inf = 1e8+1;
int n, k;
int cnt;
int depth[N];
int st[N], fi[N], f[N][N];
int dp[1 << 20];
vector<int> e[N];
void maximize(int &a, int b) { a = max(a, b); }
void go(int u, int prv = 0) {
    if (depth[u] == k) st[u] = fi[u] = ++cnt;
        else { st[u] = inf; fi[u] = -inf; }
    for(auto v: e[u]) if (depth[u] < k) {
        if (v == prv) continue;
        depth[v] = depth[u] + 1;
        go(v, u);
        st[u] = min(st[u], st[v]);
        fi[u] = max(fi[u], fi[v]);
    }
    if (st[u] != inf) maximize(f[st[u]][depth[u]], fi[u]);
}
int main() {
    ios::sync_with_stdio(0);
    cin >> n >> k;
    if (n <= k * k) { cout << "DA"; return 0; }
    repn(i, 1, n) {
        int u, v; 
        cin >> u >> v;
        e[u].pb(v);
        e[v].pb(u);
    }
    go(1);
    if (st[1] == inf) { cout << "DA"; return 0; }
    memset(dp, -1, sizeof dp);
    dp[0] = 0;
    repn(mask, 0, (1 << k)) if (dp[mask] != -1 && dp[mask] < fi[1]) 
        repn(bit, 0, k) if (!(mask >> bit & 1)) {
            int new_mask = mask | (1 << bit);
            maximize(dp[new_mask], f[dp[mask]+1][bit+1]);
        }
    repn(mask, 0, (1 << k)) if (dp[mask] == fi[1]) {
        cout << "DA";
        return 0;
    }
    cout << "NE";
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4600 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 4856 KB Output is correct
6 Correct 6 ms 4472 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4600 KB Output is correct
2 Correct 16 ms 4756 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 16 ms 4728 KB Output is correct
6 Correct 6 ms 4984 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4652 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 4728 KB Output is correct
6 Correct 6 ms 4600 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4728 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 7 ms 4728 KB Output is correct
6 Correct 6 ms 4472 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4600 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 6 ms 4856 KB Output is correct
6 Correct 6 ms 4728 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4600 KB Output is correct
2 Correct 16 ms 4668 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 6 ms 4908 KB Output is correct
6 Correct 6 ms 4728 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4604 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 16 ms 4600 KB Output is correct
6 Correct 6 ms 4700 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4600 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 392 KB Output is correct
5 Correct 6 ms 4728 KB Output is correct
6 Correct 6 ms 4856 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4600 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 392 KB Output is correct
5 Correct 6 ms 4728 KB Output is correct
6 Correct 6 ms 4728 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4600 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 11 ms 4600 KB Output is correct
6 Correct 6 ms 4600 KB Output is correct