제출 #1190551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190551		Ghulam_Junaid	Wells (CEOI21_wells)	C++20	0 / 100	26 ms	1508 KiB

wells

#include <bits/stdc++.h>
using namespace std;

const int N = 5005;
int n, k, dist[N][N];
vector<int> g[N], vec;

void dfs(int v, int r, int p = -1){
    for (int u : g[v]){
        if (u == p) continue;
        dist[r][u] = dist[r][v] + 1;
        dfs(u, r, v);
    }
}

int main(){
    cin >> n >> k;

    for (int i = 0; i < n - 1; i ++){
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int r = 1; r <= n; r ++)
        dfs(r, r);

    int mx = 0;
    for (int u = 1; u <= n; u ++)
        for (int v = 1; v <= n; v ++)
            mx = max(mx, dist[u][v]);

    if (mx < k - 1){
        cout << "YES" << endl << 0 << endl;
        return 0;
    }

    for (int i = 1; i <= n; i ++){
        vec.clear();
        for (int v = 1; v <= n; v ++)
            if (dist[i][v] % k == 0)
                vec.push_back(v);

        bool bad_root = 0;
        for (int u = 1; u <= n; u ++){
            for (int v = 1; v <= n; v ++){
                if (dist[u][v] != k - 1) continue;
                
                int cnt = 0;
                for (int x : vec)
                    cnt += (dist[u][v] == dist[u][x] + dist[x][v]);

                bad_root |= (cnt != 1);
            }
        }

        if (bad_root) continue;
        cout << "YES" << endl << 1 << endl;
        return 0;
    }
    cout << "NO" << endl << 0 << endl;
    return 0;
}

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