Submission #914944

#	Time	Username	Problem	Language	Result	Execution time	Memory
914944		Red0	Burza (COCI16_burza)	C++17	0 / 160	37 ms	1112 KiB

burza

#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((sz(adj[node]) == 1 && node != 1) || 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: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16