oj.uz

Submission #487978

# Submission time Handle Problem Language Result Execution time Memory
487978 2021-11-17T10:15:26 Z KazamaHoang Papričice (COCI20_papricice) C++14
110 / 110
 235 ms 29204 KB 
#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 69;

bool ckmin(int& a, int b) {
    return a > b? a = b, true : false;
}

int n;
vector<int> adj[200005];
multiset<int> ancestor, other;
int d[200005];
int res = inf;

void dfs(int u, int par = -1) {
    d[u] = 1;
    for (int& v : adj[u]) if (v != par) {
        dfs(v, u);
        d[u] += d[v];
    }
}

void DFS(int u, int par = -1) {
    // 2 node la to tien cua nhau
    if (u != 1) {
        auto it = ancestor.lower_bound(n+d[u]);
        if (it != ancestor.end()) {
            int s = *it; s /= 2;
            int part_one = d[u];
            int part_two = n - s;
            int part_three = s - d[u];
            int mx = max({part_one, part_two, part_three});
            int mn = min({part_one, part_two, part_three});
            ckmin(res, mx - mn);
        }
        if (it != ancestor.begin()) {
            -- it;
            int s = *it; s /= 2;
            int part_one = d[u];
            int part_two = n - s;
            int part_three = s - d[u];
            int mx = max({part_one, part_two, part_three});
            int mn = min({part_one, part_two, part_three});
            ckmin(res, mx - mn);
        }        
    }

    // 2 node khong phai to tien cua nhau
    if (u != 1) {
        auto it = other.lower_bound(n-d[u]);
        if (it != other.end()) {
            int s = *it; s /= 2;
            int part_one = d[u];
            int part_two = s;
            int part_three = n - d[u] - s;
            int mx = max({part_one, part_two, part_three});
            int mn = min({part_one, part_two, part_three});
            ckmin(res, mx - mn); 
        }
        if (it != other.begin()) {
            -- it;
            int s = *it; s /= 2;
            int part_one = d[u];
            int part_two = s;
            int part_three = n - d[u] - s;
            int mx = max({part_one, part_two, part_three});
            int mn = min({part_one, part_two, part_three});
            ckmin(res, mx - mn);
        }
    }
    ancestor.insert(2*d[u]);
    for (int& v : adj[u]) if (v != par) 
        DFS(v, u);
    ancestor.erase(ancestor.find(2*d[u]));
    other.insert(2*d[u]);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; ++ i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, -1);
    DFS(1, -1);
    cout << res;
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 5200 KB Output is correct
7 Correct 4 ms 5200 KB Output is correct
8 Correct 3 ms 5200 KB Output is correct
9 Correct 4 ms 5200 KB Output is correct
10 Correct 4 ms 5200 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 5200 KB Output is correct
7 Correct 4 ms 5200 KB Output is correct
8 Correct 3 ms 5200 KB Output is correct
9 Correct 4 ms 5200 KB Output is correct
10 Correct 4 ms 5200 KB Output is correct
11 Correct 210 ms 24000 KB Output is correct
12 Correct 227 ms 23928 KB Output is correct
13 Correct 186 ms 24436 KB Output is correct
14 Correct 193 ms 24172 KB Output is correct
15 Correct 235 ms 23996 KB Output is correct
16 Correct 149 ms 23960 KB Output is correct
17 Correct 196 ms 24024 KB Output is correct
18 Correct 219 ms 29204 KB Output is correct
19 Correct 189 ms 24064 KB Output is correct
20 Correct 210 ms 23984 KB Output is correct