oj.uz

Submission #480848

# Submission time Handle Problem Language Result Execution time Memory
480848 2021-10-18T11:36:26 Z Victor Burza (COCI16_burza) C++17
48 / 160
 1000 ms 7724 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);
    }
}

void dfs2(int u,int d){
    depth_nodes[d].pb(u);
    trav(v,graph[u])if(v!=p[u])dfs2(v,d+1);
} 

set<vector<bool>> memo[401];
 
void dp(int depth, vector<bool> blocked) {
    bool all_blocked = 1;
    rep(i,0,sz(blocked)) all_blocked &= blocked[i];
    if (all_blocked) {
        cout << "DA" << endl;
        exit(0);
    }
 
    if(depth>=k)return;
 
    if (memo[depth].count(blocked)) return;
 
    vector<bool> next;
    int pos = 0;
    trav(u, depth_nodes[depth]) {
        trav(v, graph[u])if(p[u]!=v) next.pb(blocked[pos]);
        ++pos;
    }
   
    all_blocked = 1;
    rep(i,0,sz(next)) all_blocked &= next[i];
    if (all_blocked) {
        cout << "DA" << endl;
        exit(0);
    }
 
    rep(i,0,sz(next)){
        if(next[i])continue;
        if(!depth&&i)continue;
 
        next[i]=1;
        dp(depth+1,next);
        next[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);
    dfs2(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:53:5: note: in expansion of macro 'rep'
   53 |     rep(i,0,sz(blocked)) all_blocked &= blocked[i];
      |     ^~~
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:71:5: note: in expansion of macro 'rep'
   71 |     rep(i,0,sz(next)) all_blocked &= next[i];
      |     ^~~
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:77:5: note: in expansion of macro 'rep'
   77 |     rep(i,0,sz(next)){
      |     ^~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1280 KB Output is correct
2 Correct 529 ms 7576 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 92 ms 452 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 7532 KB Output is correct
2 Correct 473 ms 7460 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 96 ms 592 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 7468 KB Output is correct
2 Correct 466 ms 7688 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Execution timed out 1086 ms 3928 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 2116 KB Output is correct
2 Correct 518 ms 7512 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 51 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 7496 KB Output is correct
2 Correct 483 ms 7568 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 16 ms 480 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 7620 KB Output is correct
2 Correct 486 ms 7648 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 11 ms 412 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 7588 KB Output is correct
2 Correct 481 ms 7528 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 428 ms 1820 KB Output isn't correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 2240 KB Output is correct
2 Correct 462 ms 7724 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 36 ms 580 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1156 KB Output is correct
2 Correct 523 ms 7500 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 25 ms 480 KB Output is correct
6 Correct 543 ms 2368 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 4000 KB Output is correct
2 Correct 490 ms 7596 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct