oj.uz

Submission #757246

# Submission time Handle Problem Language Result Execution time Memory
757246 2023-06-12T21:03:52 Z spicymango Burza (COCI16_burza) C++17
64 / 160
 58 ms 844 KB 
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <deque>
#include <unordered_set>
#include <cctype>
#include <unordered_map>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <set>
#include <map>
#include <limits.h>
#include <cctype>
#include <cmath>
#include <bit>
#include <queue>
#include <numeric>
#include <iomanip>
using namespace std;
using ll = long long;
using ul = unsigned long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using qi = queue<int>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using di = deque<int>;
using dpi = deque<pii>;
using vpi = vector<pii>;
using tii = tuple<int, int, int>;
using vti = vector<tii>;
using qpi = queue<pii>;
using qti = queue<tii>;
using si = unordered_set<int>;
using sll = unordered_set<ll>;
using osll = set<ll>;
using osi = set<int>;
using osp = set<pii>;
using mosi = multiset<int>;
using mosc = multiset<char>;
using mpi = map<pii, int>;
using mip = map<int, pii>;
using miv = unordered_map<int, vi>;
using mii = unordered_map<int, int>;
using mill = unordered_map<int, ll>;
#define lso(S) ((S) & -(S))
const int MOD = 1e9 + 7;
const int F = 1e5;
const ll INF = 1e18;

vvi AL{};
vvi atdepth{};
int nleaves = 0;
pii intervals[401]{};
int dp[(1 << 20)]{};
int n, k;

void dfs(int u, int d, int p){
    if (d == k) {
        intervals[u] = {nleaves, nleaves + 1};
        ++nleaves;
        atdepth[k].push_back(u);
        return;
    }
    atdepth[d].push_back(u);
    intervals[u].first = 500;
    intervals[u].second = 0;
    for (int v: AL[u]){
        if (v == p) continue;
        dfs(v, d + 1, u);
        intervals[u].first = min(intervals[u].first, intervals[v].first);
        intervals[u].second = max(intervals[u].second, intervals[v].second);
    }
    // if (intervals[u].first == 500) { // depth is less than k and no children
    //     intervals[u].f
    // }
}
void solve(){
    scanf("%d %d", &n, &k);
    AL.assign(n, vi());
    atdepth.assign(k + 1, vi());
    for (int i = 0; i < n - 1; ++i){
        int u, v; scanf("%d %d", &u, &v); --u; --v;
        AL[u].push_back(v);
        AL[v].push_back(u);
    }
    dfs(0, 0, -1);
    // for (int i = 0; i < n; ++i){
    //     printf("%d %d %d\n", i, intervals[i].first, intervals[i].second);
    // }
    if (k * k > n) {printf("DA\n"); return;}
    for (ll s = 1; s < (1 << k); ++s){
        for (int j = 1; j <= k; ++j){
            if (!(s & 1 << j)) continue;
            int prev_int = dp[s ^ j];
            for (int node : atdepth[j]){
                if (intervals[node].first <= prev_int) {
                    dp[s] = max(dp[s], intervals[node].second);
                }
            }
        }
    }
    if (dp[(1 << k) - 1] == nleaves) printf("DA\n");
    else printf("NE\n");
}
 
/*
    Did you read all of the input?
    Did you reset your data structures?
    Are your early exits correct?
    Is overflow possible?
    What happens for small n?
    Are you zero/one indexing correctly?
*/
int main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    solve(); return 0;
    int tc; scanf("%d", &tc);
    while (tc--){
        solve();
    }
} 

// g++ -o tmp tmp.cpp -fsanitize=undefined -std=c++20
// Extra debugging: -Wall -Wextra -Wshadow -Wconversion -Wfloat-equal -Wduplicated-cond -Wlogical-op

Compilation message

burza.cpp: In function 'void solve()':
burza.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
burza.cpp:88:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         int u, v; scanf("%d %d", &u, &v); --u; --v;
      |                   ~~~~~^~~~~~~~~~~~~~~~~
burza.cpp: In function 'int main()':
burza.cpp:124:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |     int tc; scanf("%d", &tc);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 50 ms 764 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 724 KB Output is correct
2 Correct 45 ms 836 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Incorrect 58 ms 844 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 716 KB Output is correct
2 Correct 49 ms 816 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 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 53 ms 828 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 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 756 KB Output is correct
2 Correct 50 ms 840 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 308 KB Output is correct
6 Correct 1 ms 300 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 840 KB Output is correct
2 Correct 49 ms 836 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 1 ms 212 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 728 KB Output is correct
2 Correct 55 ms 716 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Incorrect 47 ms 800 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 47 ms 832 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 54 ms 844 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 520 KB Output is correct
2 Correct 46 ms 736 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Incorrect 19 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -