Submission #1131110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131110		henrlly	Burza (COCI16_burza)	C++20	0 / 160	1 ms	324 KiB

burza

// time-limit: 3000
#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <unordered_map>

using namespace std;

#define ll long long

using vll = vector<ll>;
using vvll = vector<vector<ll> >;
using mpll = map<pair<ll, ll>, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pi = pair<int, int>;

void setIO(string name = "") {
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

void solve() {
    return;
}
unordered_map<int, vi> m;
vi depths;
unordered_map<int, unordered_map<int, vi> > bb;
int bi = 0;

int dfs(int x, int prev, int depth, int bi) {
    int d = depth;
    bool ub = false;
    if (prev == -1 || m[x].size() > 2) ub = true;
    for (auto &e: m[x]) {
        if (e != prev) {
            if (ub) bb[bi][depth].push_back(e);
            d = max(d, dfs(e, x, depth + 1, ub ? e : bi));
        }
    }
    depths[x] = d;
    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // setIO("test");

    int n, k;
    cin >> n >> k;
    depths.resize(n+1);
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        m[a].push_back(b);
    }

    dfs(1, -1, 0, 1);
    set<pair<int,int>, greater<pair<int,int> > > pq;
    for (auto &branch: bb[1][0]) {
        pq.insert({depths[branch], branch});
    }
    int curd = 1;
    int steps = 0;
    while (!pq.empty() && steps <= k+1) {
        pq.erase(pq.begin());
        vi v;
        for (auto &[d, b]: pq) {
            for (auto &e: bb[b][curd]) {
                v.push_back(e);
            }
        }
        for (auto &e: v) pq.insert({depths[e], e});
        steps++;
        curd++;
    }

    cout << (steps == k+1 ? "NE" : "DA") << endl;

    return 0;
}

Compilation message (stderr)

burza.cpp: In function 'void setIO(std::string)':
burza.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
burza.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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