oj.uz

Submission #914945

# Submission time Handle Problem Language Result Execution time Memory
914945 2024-01-23T01:59:40 Z Red0 Burza (COCI16_burza) C++17
160 / 160
 39 ms 860 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

//debug template
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

//hashing
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x^(x>>30))*0xbf58476d1ce4e5b9;
        x = (x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = rng();
        return splitmix64(x+FIXED_RANDOM);
    }
};

//data structures
//using namespace __gnu_pbds;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using safe_set = unordered_set<T, custom_hash>;
template<typename T, typename V> using safe_map = unordered_map<T, V, custom_hash>;

//permanent definitions
typedef long long ll;
using pii = pair<int, int>; using pil = pair<int, ll>; using pll = pair<ll, ll>;
using vi = vector<int>; using vll = vector<ll>; using vc = vector<char>; using vs = vector<string>; using vpi = vector<pii>;
using vvi = vector<vi>; using vvl = vector<vll>; using vvc = vector<vc>;
#define repl(i, a, b) for(int i = a; i < b; ++i)
#define repe(i, a, b) for(int i = a; i <= b; ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define mp make_pair
#define f first
#define s second
//temporary definitions
const int INF = 1000000005;
const ll MAX_N = 405, MAX_K = 405;

int n, k, cntr = 0;
vvi adj(MAX_N), depth(MAX_N);
vpi range(MAX_N, {INF, 0});

vi dfs(int parent, int node, int d) {
    if(d == k) {
        depth[d].pb(node);
        range[node] = mp(++cntr, cntr);
        return vi{node};
    }
    vi vals;
    trav(next, adj[node]) {
        if(next != parent) {
            vi res = dfs(node, next, d+1);
            trav(v, res) {
                vals.pb(v);
            }
        }
    }
    trav(cur, vals) {
        range[node].f = min(range[node].f, range[cur].f);
        range[node].s = max(range[node].s, range[cur].s);
    }
    depth[d].pb(node);
    return vals;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    //ifstream cin("input.in");
    cin >> n >> k;

    if(k*k >= n) {
        cout << "DA\n";
        return 0;
    }

    repl(i, 0, n-1) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    auto vals = dfs(0, 1, 0);
    debug(range[1]);
    vi dp(1<<k);
    dp[0] = 0;
    repl(i, 1, 1<<k) {
        repl(j, 0, k) {
            if((i>>j)&1) {
                auto prev = dp[i & ~(1<<j)];
                //debug(i & ~(1<<j));
                //debug(prev);
                trav(node, depth[j+1]) {
                    //debug(node);
                    //debug(prev.f);
                    //debug(convert[range[node].s]);
                    //debug(convert[range[node].f]);
                    if(range[node].f <= prev+1) {
                        dp[i] = max(dp[i], range[node].s);
                    }
                }
            }
        }
        //debug(res);
        if(dp[i] == sz(depth[k])) {
            //debug(dp[i]);
            cout << "DA\n";
            return 0;
        }
    }

    //debug(dp);

    cout << "NE\n";

    return 0;
}

/*
list of data structures:
vectors
arrays
adjacency list
adjacency matrix
edge list
maps
unordered maps
sets((mono) -> insert, erase)
multisets
ordered sets(() -> insert, erase, find_by_order)
unordered sets
queues
deques
priority queues
stacks(mono)
heaps(min, max)
disjoint set union
binary search trees
spanning trees(min, max)
fenwick trees(sum, diff)
segment trees(sum, diff, min, max, xor)
tries
linked lists

list of algorithms:
prefix/suffix sums(sum, diff, min, max, 1d, 2d)
coordinate compression
binary search/BSTA
dp(knapsack, paths on grid, LIS, range, bitwise, digit)
two pointers
sliding window
recursion
dfs(floodfill)
bfs
trees(diameters)
sweep line
*/

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 37 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 860 KB Output is correct
2 Correct 39 ms 860 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 36 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 860 KB Output is correct
2 Correct 37 ms 856 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 604 KB Output is correct
2 Correct 37 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 860 KB Output is correct
2 Correct 35 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 860 KB Output is correct
2 Correct 36 ms 860 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 860 KB Output is correct
2 Correct 35 ms 856 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 37 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 604 KB Output is correct
2 Correct 36 ms 860 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 412 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 38 ms 860 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 604 KB Output is correct
2 Correct 37 ms 860 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 16 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct