oj.uz

Submission #680319

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

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

int depth[1500006], ds[1500006];

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

bool dfs(int x, int par, int prev = -1) {
    if (b[x]) {
        if (par == -1) par = x;
        else {
            int dist = ds[par] - ds[x];
            if (dist % K) return false;
            if (k % 2 == 0) {
                int r = dist % k;
                if (b[x] == 3) {
                    if (r) b[x] = 3 - b[par];
                    else b[x] = b[par];
                } else if ((r ? 1 : 0) != (b[par] != b[x])) return false;
            }
            par = x;
        }
    }
    for (auto &i: adj[x]) if (i != prev && !dfs(i, par, x)) return false;
    return true;
}

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) {
        if (k % 2) {
            b[i] = 1;
            continue;
        }
        for (int j = 0; j < n; j++) depth[j] = 0;
        ds[i] = 0, dfs_depth(i);
        int cnt = 0;
        for (auto &j: adj[i]) if (depth[j] + 1 < k / 2) cnt++;
        if ((int)adj[i].size() - cnt < 3) continue;
        for (int j = 0; j < n; j++) if (ds[j] == k / 2) cnt++;
        if (cnt > (int)adj[i].size()) b[i] = 1;
        else b[i] = 3;
    }
    //for (int i = 0; i < n; i++) printf("%d=%d\n", i + 1, b[i]);
    int k = -1;
    for (int i = 0; i < n; i++) if (b[i] == 1) k = i;
    if (k == -1) for (int i = 0; i < n; i++) if (b[i]) k = i;
    if (k == -1) return puts("YES\n1"), 0;
    b[k] = 1;
    for (int j = 0; j < n; j++) depth[j] = 0;
    ds[k] = 0, dfs_depth(k);
    puts(dfs(k, -1) ? "YES\n1" : "NO\n0");
}

Compilation message

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

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 22 ms 35540 KB Output is partially correct
2 Partially correct 22 ms 35540 KB Output is partially correct
3 Partially correct 22 ms 35548 KB Output is partially correct
4 Partially correct 20 ms 35540 KB Output is partially correct
5 Partially correct 22 ms 35540 KB Output is partially correct
6 Partially correct 26 ms 35560 KB Output is partially correct
7 Correct 22 ms 35488 KB Output is correct
8 Correct 21 ms 35432 KB Output is correct
9 Incorrect 23 ms 35508 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 22 ms 35540 KB Output is partially correct
2 Partially correct 22 ms 35540 KB Output is partially correct
3 Partially correct 22 ms 35548 KB Output is partially correct
4 Partially correct 20 ms 35540 KB Output is partially correct
5 Partially correct 22 ms 35540 KB Output is partially correct
6 Partially correct 26 ms 35560 KB Output is partially correct
7 Correct 22 ms 35488 KB Output is correct
8 Correct 21 ms 35432 KB Output is correct
9 Incorrect 23 ms 35508 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 22 ms 35540 KB Output is partially correct
2 Partially correct 22 ms 35540 KB Output is partially correct
3 Partially correct 22 ms 35548 KB Output is partially correct
4 Partially correct 20 ms 35540 KB Output is partially correct
5 Partially correct 22 ms 35540 KB Output is partially correct
6 Partially correct 26 ms 35560 KB Output is partially correct
7 Correct 22 ms 35488 KB Output is correct
8 Correct 21 ms 35432 KB Output is correct
9 Incorrect 23 ms 35508 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 22 ms 35540 KB Output is partially correct
2 Partially correct 22 ms 35540 KB Output is partially correct
3 Partially correct 22 ms 35548 KB Output is partially correct
4 Partially correct 20 ms 35540 KB Output is partially correct
5 Partially correct 22 ms 35540 KB Output is partially correct
6 Partially correct 26 ms 35560 KB Output is partially correct
7 Correct 22 ms 35488 KB Output is correct
8 Correct 21 ms 35432 KB Output is correct
9 Incorrect 23 ms 35508 KB Output isn't correct
10 Halted 0 ms 0 KB -