oj.uz

Submission #480853

# Submission time Handle Problem Language Result Execution time Memory
480853 2021-10-18T11:53:07 Z Victor Burza (COCI16_burza) C++17
16 / 160
 1000 ms 14944 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int n, k, p[401], md[401];
vi graph[401], s_graph[401];
vi depth_nodes[401];

void dfs(int u, int d) {
    md[u] = d;
    trav(v, s_graph[u]) if (v != p[u]) {
        p[v] = u;
        dfs(v, d + 1);
        md[u] = max(md[u], md[v]);
        if (md[v] >= k) graph[u].pb(v);
    }
    if(md[u]>=k)depth_nodes[d].pb(u);
}

set<vector<bool>> memo[401];

void dp(int depth, vector<bool> blocked) {
    if (depth == k) return;
    if(memo[depth].count(blocked))return;

    vector<bool> nxt;
    int pos = 0;
    int cnt=sz(depth_nodes[depth+1]);
    trav(u, depth_nodes[depth]) {
        bool bp=blocked[pos];
        cnt-=sz(graph[u])*bp;
        trav(v, graph[u])if(v!=p[u]) nxt.pb(bp);
        ++pos;
    }

    if(cnt<=1){
        cout<<"DA"<<endl;
        exit(0);
    }

    rep(i,0,sz(nxt)){
        if(nxt[i])continue;
        nxt[i]=1;
        dp(depth+1,nxt);
        nxt[i]=0;
    }

    memo[depth].insert(blocked);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n >> k;
    rep(i, 0, n - 1) {
        int u, v;
        cin >> u >> v;
        s_graph[--u].pb(--v);
        s_graph[v].pb(u);
    }

    dfs(0, 0);
    dp(0, vector<bool>(sz(depth_nodes[0]), 0));

    cout << "NE" << endl;
    return 0;
}

Compilation message

burza.cpp: In function 'void dp(int, std::vector<bool>)':
burza.cpp:5:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i, a, b) for (int i = (a); i < (b); ++i)
      |                                          ^
burza.cpp:66:5: note: in expansion of macro 'rep'
   66 |     rep(i,0,sz(nxt)){
      |     ^~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 2240 KB Output is correct
2 Correct 975 ms 14724 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 44 ms 516 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 14624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 989 ms 14660 KB Output is correct
2 Correct 994 ms 14920 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Execution timed out 1087 ms 6240 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 4100 KB Output is correct
2 Execution timed out 1050 ms 14804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 14784 KB Output is correct
2 Correct 990 ms 14804 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Execution timed out 1098 ms 5180 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 14676 KB Output is correct
2 Execution timed out 1000 ms 14732 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 14944 KB Output is correct
2 Correct 988 ms 14708 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Execution timed out 1088 ms 5512 KB Time limit exceeded

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 4036 KB Output is correct
2 Execution timed out 1006 ms 14700 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 2212 KB Output is correct
2 Execution timed out 1071 ms 14652 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 7468 KB Output is correct
2 Execution timed out 1063 ms 14672 KB Time limit exceeded
3 Halted 0 ms 0 KB -