oj.uz

Submission #744358

# Submission time Handle Problem Language Result Execution time Memory
744358 2023-05-18T13:37:39 Z hmm789 Wells (CEOI21_wells) C++14
0 / 100
 41 ms 35588 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
#define INF 1000000000000000000
 
vector<int> adj[1500000], v0;
int clr[1500000], depth[1500000], n, k, mx;
bool ok, used[1500000];
 
int dfs(int x, int p, int c) {
    clr[x] = c;
    if(c == 0) v0.push_back(x);
    depth[x] = 0;
    for(int i : adj[x]) if(i != p) {
        depth[x] = max(depth[x], dfs(i, x, (c+1)%k)+1);
    }
    return depth[x];
}
 
pair<int, int> dfs2(int x, int p) {
    pair<int, int> ans = {INF, -INF};
    vector<int> v, v2, v3;
    for(int i : adj[x]) if(i != p) {
        pair<int, int> tmp = dfs2(i, x);
        if(tmp.second == -INF) {
            v2.push_back(depth[i]);
        } else {
            ans.first = min(ans.first, tmp.first+1);
            ans.second = max(ans.second, tmp.second+1);
            v.push_back(tmp.first);
            v3.push_back(tmp.second);
        }
    }
    if(clr[x]) {
        sort(v3.rbegin(), v3.rend());
        if(v3.size() > 1 && v3[0]+v3[1]+1 >= k) ok = false;
        sort(v.begin(), v.end());
        if(v.size() > 1 && v[0]+v[1]+3 <= k) ok = false;
        sort(v2.rbegin(), v2.rend());
        if(v2.size() > 1 && v2[0]+v2[1]+3 >= k) ok = false;
        if(v2.size() && v3.size() && v2[0]+v3[0]+2 >= k) ok = false;
    }
    if(clr[x] == 0) return {0, 0};
    else return ans;
}
 
int dfs3(int x, int p) {
    int ans = 1;
    vector<int> v;
    for(int i : adj[x]) if(i != p) {
        int tmp = dfs3(i, x);
        v.push_back(tmp);
        ans = max(ans, tmp+1);
    }
    if(p == -1) {
        sort(v.rbegin(), v.rend());
        if(v.size() > 0) mx = max(mx, v[0]+1);
        if(v.size() > 1) mx = max(mx, v[0]+v[1]+1);
    }
    return ans;
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int x, y, ans = 0, mult = 1, cnt = 0;
    cin >> n >> k;
    for(int i = 0; i < n-1; i++) {
        cin >> x >> y;
        x--; y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i = 0; i < n; i++) {
        if(used[i]) continue;
        mx = 0;
        dfs3(i, -1);
        if(mx < k) {
            cnt++;
            mult = (2*mult)%MOD;
            continue;
        }
        v0.clear();
        dfs(i, -1, 0);
        ok = true;
        dfs2(i, -1);
        if(ok) {
            ans++;
            for(int j : v0) used[j] = true;
        }
    }
    if(cnt == n) {
        cout << "YES\n" << mult << '\n';
        return 0;
    }
    if(ans == 0) cout << "NO\n";
    else cout << "YES\n";
    cout << (ans*mult)%MOD << '\n';
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35540 KB Output is correct
2 Partially correct 25 ms 35576 KB Output is partially correct
3 Partially correct 24 ms 35588 KB Output is partially correct
4 Correct 26 ms 35552 KB Output is correct
5 Partially correct 25 ms 35480 KB Output is partially correct
6 Partially correct 22 ms 35520 KB Output is partially correct
7 Correct 41 ms 35544 KB Output is correct
8 Correct 23 ms 35528 KB Output is correct
9 Correct 25 ms 35484 KB Output is correct
10 Correct 25 ms 35540 KB Output is correct
11 Incorrect 26 ms 35560 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 18 ms 35540 KB Output is correct
2 Partially correct 25 ms 35576 KB Output is partially correct
3 Partially correct 24 ms 35588 KB Output is partially correct
4 Correct 26 ms 35552 KB Output is correct
5 Partially correct 25 ms 35480 KB Output is partially correct
6 Partially correct 22 ms 35520 KB Output is partially correct
7 Correct 41 ms 35544 KB Output is correct
8 Correct 23 ms 35528 KB Output is correct
9 Correct 25 ms 35484 KB Output is correct
10 Correct 25 ms 35540 KB Output is correct
11 Incorrect 26 ms 35560 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 18 ms 35540 KB Output is correct
2 Partially correct 25 ms 35576 KB Output is partially correct
3 Partially correct 24 ms 35588 KB Output is partially correct
4 Correct 26 ms 35552 KB Output is correct
5 Partially correct 25 ms 35480 KB Output is partially correct
6 Partially correct 22 ms 35520 KB Output is partially correct
7 Correct 41 ms 35544 KB Output is correct
8 Correct 23 ms 35528 KB Output is correct
9 Correct 25 ms 35484 KB Output is correct
10 Correct 25 ms 35540 KB Output is correct
11 Incorrect 26 ms 35560 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 18 ms 35540 KB Output is correct
2 Partially correct 25 ms 35576 KB Output is partially correct
3 Partially correct 24 ms 35588 KB Output is partially correct
4 Correct 26 ms 35552 KB Output is correct
5 Partially correct 25 ms 35480 KB Output is partially correct
6 Partially correct 22 ms 35520 KB Output is partially correct
7 Correct 41 ms 35544 KB Output is correct
8 Correct 23 ms 35528 KB Output is correct
9 Correct 25 ms 35484 KB Output is correct
10 Correct 25 ms 35540 KB Output is correct
11 Incorrect 26 ms 35560 KB Output isn't correct
12 Halted 0 ms 0 KB -