oj.uz

답안 #914935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914935 2024-01-23T01:44:24 Z Red0 Burza (COCI16_burza) C++17
0 / 160
 509 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

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 344 KB Output is correct
2 Correct 509 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 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 423 ms 860 KB Output is correct
2 Correct 429 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 412 ms 860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 434 ms 856 KB Output is correct
2 Correct 431 ms 856 KB Output is correct
3 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 604 KB Output is correct
2 Correct 470 ms 860 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 427 ms 860 KB Output is correct
2 Correct 485 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 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 485 ms 860 KB Output is correct
2 Correct 462 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 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 413 ms 856 KB Output is correct
2 Correct 418 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 437 ms 860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 604 KB Output is correct
2 Correct 409 ms 856 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 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

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 348 KB Output is correct
2 Correct 478 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 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 604 KB Output is correct
2 Correct 451 ms 856 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 185 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -