oj.uz

Submission #680297

# Submission time Handle Problem Language Result Execution time Memory
680297 2023-01-10T14:12:50 Z mjhmjh1104 Wells (CEOI21_wells) C++17
0 / 100
 19 ms 35452 KB 
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

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

bool dfs(int x, int dist, int prev = -1) {
    if (b[x]) {
        if (dist != -1 && dist % K) return false;
        dist = 0;
    }
    int ndist = dist;
    if (ndist != -1) ndist++;
    for (auto &i: adj[x]) if (i != prev && !dfs(i, ndist, x)) return false;
    return true;
}

int depth[1500006];

int dfs_depth(int x, int prev = -1) {
    for (auto &i: adj[x]) if (i != prev) depth[x] = max(depth[x], dfs_depth(i, x) + 1);
    return depth[x];
}

int main() {
    scanf("%d%d", &n, &k);
    K = k;
    if (k % 2 == 0) K /= 2;
    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);
    }
    for (int i = 0; i < n; i++) if ((int)adj[i].size() > 2) {
        dfs_depth(i);
        vector<int> v;
        for (auto &j: adj[i]) v.push_back(depth[j] + 1);
        int cnt = 0;
        swap(v.back(), *max_element(v.begin(), v.end()));
        cnt += v.back(); v.pop_back();
        swap(v.back(), *max_element(v.begin(), v.end()));
        cnt += v.back(); v.pop_back();
        if (cnt + 1 >= k) b[i] = 1;
    }
    for (int i = 0; i < n; i++) if (!dfs(i, -1)) return puts("NO\n0"), 0;
    puts("YES\n1");
}

Compilation message

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

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 18 ms 35400 KB Output is partially correct
2 Incorrect 19 ms 35452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 18 ms 35400 KB Output is partially correct
2 Incorrect 19 ms 35452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 18 ms 35400 KB Output is partially correct
2 Incorrect 19 ms 35452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 18 ms 35400 KB Output is partially correct
2 Incorrect 19 ms 35452 KB Output isn't correct
3 Halted 0 ms 0 KB -