oj.uz

Submission #914934

# Submission time Handle Problem Language Result Execution time Memory
914934 2024-01-23T01:41:32 Z vjudge1 Burza (COCI16_burza) C++17
0 / 160
 532 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;
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 || d == k) {
        depth[d].pb(node);
        range[node] = mp(node, node);
        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(vals);
    safe_map<int, int> convert;
    repe(i, 1, sz(vals)) {
        convert[vals[i-1]] = i;
    }

    //debug(convert);
    debug(convert[range[1].f]);
    debug(convert[range[1].s]);

    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(convert[range[node].f] <= prev+1) {
                        dp[i] = max(dp[i], convert[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.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 544 KB Output is correct
2 Correct 494 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 Incorrect 2 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 860 KB Output is correct
2 Correct 440 ms 860 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 437 ms 860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 860 KB Output is correct
2 Correct 532 ms 860 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 604 KB Output is correct
2 Correct 493 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 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 860 KB Output is correct
2 Correct 441 ms 856 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 2 ms 356 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 860 KB Output is correct
2 Correct 432 ms 856 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 856 KB Output is correct
2 Correct 384 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 Incorrect 473 ms 860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 600 KB Output is correct
2 Correct 520 ms 856 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 348 KB Output is correct
2 Correct 505 ms 860 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 600 KB Output is correct
2 Correct 493 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 Incorrect 213 ms 600 KB Output isn't correct
6 Halted 0 ms 0 KB -