oj.uz

Submission #1088197

# Submission time Handle Problem Language Result Execution time Memory
1088197 2024-09-14T05:52:37 Z MercubytheFirst Wells (CEOI21_wells) C++17
0 / 100
 19 ms 812 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define endl '\n'

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 37
#endif

const ll N = 203;
vector<vector<ll> > g;
ll n, k;
ll dist[N][N];
vector<ll> max_dist;
vector<bool> marked;

ll dist_calc(const ll source, ll v, ll p) {
    dist[source][v] = dist[source][p] + 1;
    pair<ll, ll> mx{0, 0};
    for(ll to : g[v]) {
        if(to != p) {
            dist_calc(source, to, v);
            mx = max({mx, {mx.first, max_dist[to] + 1}, {max_dist[to] + 1, mx.first}});
        }
    }
    max_dist[v] = mx.first;
    return mx.first + mx.second;
}

bool check_dfs(ll v, ll p, ll d) {
    if(marked[v]) {
        return true;
    }
    if(d + 1 >= k) {
        return false;
    }
    bool ok = true;
    for(ll to : g[v]) {
        if(to != p and !marked[to]) {
            ok &= check_dfs(to, v, d + 1);
            if(!ok) {
                break;
            }
        }
    }
    return ok;
}

vector<ll> mark_set(ll x) {
    vector<ll> res;
    marked.assign(n + 1, false);
    for(ll i = 1; i <= n; ++i) {
        if(dist[x][i] % k == 0) {
            marked[i] = true;
            res.push_back(i);
        }
    }
    return res;
}

const ll mod = 1e9 + 7;
inline void solve(){
    memset(dist, -1, sizeof(dist));
    cin >> n >> k;
    if(n > 200) {
        cout << "NO\n0\n";
        return;
    }
    g.assign(n + 1, vector<ll>());
    for(ll i = 1; i < n; ++i) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<bool> useless(n + 1);
    for(ll i = 1; i <= n; ++i) {
        max_dist.assign(n + 1, 0);
        ll len = dist_calc(i, i, 0);
        if(len + 1 < k) {
            useless[i] = true;
        }
    }
    ll ans = 0;
    if(count(useless.begin() + 1, useless.end(), true) == n) {
        ans = 1;
        for(ll i = 1; i <= n; ++i) {
            ans = ans * 2 % mod;
        }
        cout << "YES\n"
             << ans << '\n';
        return;
    }
    for(ll u = 1; u <= n; ++u) {
        if(useless[u]) {
            continue;
        }
        vector<ll> marked_vertices = mark_set(u);
        const ll m = marked_vertices.size();
        bool ok = true;
        for(ll i = 0; i < m; ++i) {
            if(marked_vertices[i] < u) {
                ok = false;
                break;
            }
            for(ll j = 0; j < i; ++j) {
                if(dist[marked_vertices[i]][marked_vertices[j]] % k) {
                    ok = false;
                    break;
                }
            }
            if(!ok) {
                break;
            }
        }
        for(ll i = 1; i <= n; ++i) {
            if(!marked[i] and !check_dfs(i, -1, 0)) {
                ok = false;
                break;
            }
        }
        debug(u, ok);
        ans += ok;
    }
    for(ll i = 1; i <= n; ++i) {
        if(useless[i]) {
            ans = ans * 2 % mod;
        }
    }
    cout << (ans ? "YES\n" : "NO\n") << ans << endl;

}

 
signed main(){
    #ifdef LOCAL
    freopen("test.in", "r",  stdin);
    freopen("err.txt", "w", stderr);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); 
    // signed t; cin >> t; while(t--)
        solve();
}

Compilation message

wells.cpp: In function 'void solve()':
wells.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 37
      |                    ^~
wells.cpp:124:9: note: in expansion of macro 'debug'
  124 |         debug(u, ok);
      |         ^~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Partially correct 6 ms 604 KB Output is partially correct
3 Partially correct 19 ms 812 KB Output is partially correct
4 Correct 5 ms 600 KB Output is correct
5 Partially correct 6 ms 808 KB Output is partially correct
6 Partially correct 12 ms 604 KB Output is partially correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 804 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Incorrect 1 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Partially correct 6 ms 604 KB Output is partially correct
3 Partially correct 19 ms 812 KB Output is partially correct
4 Correct 5 ms 600 KB Output is correct
5 Partially correct 6 ms 808 KB Output is partially correct
6 Partially correct 12 ms 604 KB Output is partially correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 804 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Incorrect 1 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Partially correct 6 ms 604 KB Output is partially correct
3 Partially correct 19 ms 812 KB Output is partially correct
4 Correct 5 ms 600 KB Output is correct
5 Partially correct 6 ms 808 KB Output is partially correct
6 Partially correct 12 ms 604 KB Output is partially correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 804 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Incorrect 1 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Partially correct 6 ms 604 KB Output is partially correct
3 Partially correct 19 ms 812 KB Output is partially correct
4 Correct 5 ms 600 KB Output is correct
5 Partially correct 6 ms 808 KB Output is partially correct
6 Partially correct 12 ms 604 KB Output is partially correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 804 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Incorrect 1 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -