Submission #680288

#	Time	Username	Problem	Language	Result	Execution time	Memory
680288		mjhmjh1104	Wells (CEOI21_wells)	C++17	0 / 100	18 ms	35716 KiB

wells

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int n, k;
vector<int> adj[1500006];

pair<int, int> dfs(int x, int prev = -1) {
    pair<int, int> res = { 0, 0 };
    vector<int> v;
    for (auto &i: adj[x]) if (i != prev) {
        pair<int, int> curr = dfs(i, x);
        res.first += curr.first;
        res.second = max(res.second, curr.second + 1);
        v.push_back(curr.second + 1);
    }
    bool fl = false;
    int curr = 0;
    if (!v.empty()) {
        swap(v.back(), *max_element(v.begin(), v.end()));
        curr += v.back(); v.pop_back();
    }
    if (!v.empty()) {
        swap(v.back(), *max_element(v.begin(), v.end()));
        curr += v.back(); v.pop_back();
    }
    if (curr >= k) fl = true;
    if (fl) res.first++, res.second = -1;
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int res = 0;
    for (int i = 0; i < n; i++) res = max(res, (int)adj[i].size());
    if (res <= 2 || k == 1) return puts("YES"), 0;
    k--;
    if (dfs(0).first >= 2) puts("NO");
    else puts("YES");
}

Compilation message (stderr)

wells.cpp: In function 'int main()':
wells.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
wells.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30