Submission #480851

#	Time	Username	Problem	Language	Result	Execution time	Memory
480851		Victor	Burza (COCI16_burza)	C++17	0 / 160	1100 ms	46828 KiB

burza

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int n, k, p[401], md[401];
vi graph[401], s_graph[401];

void dfs(int u, int d) {
    md[u] = d;
    trav(v, s_graph[u]) if (v != p[u]) {
        p[v] = u;
        dfs(v, d + 1);
        md[u] = max(md[u], md[v]);
        if (md[v] >= k) graph[u].pb(v);
    }
}

set<list<int>> memo[401];

void dp(int depth, list<int> nodes) {
    if (depth >= k) return;
    if (memo[depth].count(nodes)) return;

    list<int> nxt;
    trav(u, nodes) trav(v, graph[u]) if (p[u] != v) nxt.push_back(v);
    if (sz(nxt) <= 1) {
        cout << "DA" << endl;
        exit(0);
    }

    auto it = nxt.begin();
    rep(i, 0, sz(nxt)) {
        int val = *it;
        it = nxt.erase(it);
        dp(depth + 1, nxt);
        nxt.insert(it, val);
    }

    memo[depth].insert(nodes);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n >> k;
    rep(i, 0, n - 1) {
        int u, v;
        cin >> u >> v;
        graph[--u].pb(--v);
        graph[v].pb(u);
    }

    list<int> l;
    l.pb(0);
    dfs(0, 0);
    dp(0, l);

    cout << "NE" << endl;
    return 0;
}

Compilation message (stderr)

burza.cpp: In function 'void dp(int, std::__cxx11::list<int>)':
burza.cpp:5:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::list<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i, a, b) for (int i = (a); i < (b); ++i)
      |                                          ^
burza.cpp:57:5: note: in expansion of macro 'rep'
   57 |     rep(i, 0, sz(nxt)) {
      |     ^~~

• 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