oj.uz

Submission #150977

# Submission time Handle Problem Language Result Execution time Memory
150977 2019-09-01T13:34:40 Z letrongdat Burza (COCI16_burza) C++17
0 / 160
 17 ms 9772 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 + 1) / 2) { cout << "NE"; 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 << "NE"; 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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4728 KB Output is correct
2 Correct 16 ms 4704 KB Output is correct
3 Runtime error 13 ms 9772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4728 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Runtime error 13 ms 9636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4856 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Runtime error 13 ms 9628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4856 KB Output is correct
2 Correct 16 ms 4676 KB Output is correct
3 Runtime error 13 ms 9592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4656 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Runtime error 13 ms 9592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4728 KB Output is correct
2 Correct 16 ms 4620 KB Output is correct
3 Runtime error 13 ms 9592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4728 KB Output is correct
2 Correct 16 ms 4600 KB Output is correct
3 Runtime error 13 ms 9720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
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 Runtime error 13 ms 9720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #9
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 Runtime error 13 ms 9592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4600 KB Output is correct
2 Correct 17 ms 4600 KB Output is correct
3 Runtime error 13 ms 9592 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -