oj.uz

Submission #879790

# Submission time Handle Problem Language Result Execution time Memory
879790 2023-11-28T06:46:14 Z TAhmed33 Papričice (COCI20_papricice) C++
50 / 110
 1000 ms 34640 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
const int MAXN = 2e5 + 25;
const int bad = -1e7;
inline int comb (int a, int b, int c) {
    return abs(2 * a - c) < abs(2 * b - c) ? a : b;
}
vector <int> adj[MAXN];
int sze[MAXN], n, in[MAXN], out[MAXN], t;
set <int> dd[MAXN];
int mn = 1e9; 
void dfs (int pos, int par) {
    sze[pos] = 1;
    in[pos] = ++t;
    int mx = bad;
    for (auto j : adj[pos]) {
        if (j == par) continue;
        dfs(j, pos);
        sze[pos] += sze[j];
        if (dd[pos].size() < dd[j].size()) dd[pos].swap(dd[j]);
        for (auto i : dd[j]) dd[pos].insert(i);
        dd[j].clear();
    }
    for (auto i : dd[pos]) mx = comb(i, mx, sze[pos]);
    dd[pos].insert(sze[pos]);
    if (sze[pos] != 1 && pos != 1) mn = min(mn, max({n - sze[pos], sze[pos] - mx, mx}) - min({n - sze[pos], sze[pos] - mx, mx}));
    out[pos] = t;
}
set <int> x;
void dfs2 (int pos, int par) {
    if (pos != 1 && !x.empty()) {
        auto t = x.lower_bound((n - sze[pos]) / 2);
        int ret = bad;
        if (t != x.end()) ret = *t;
        if (t != x.begin()) {
            t--;
            ret = comb(ret, *t, n - sze[pos]);
        }
        mn = min(mn, max({sze[pos], ret, n - sze[pos] - ret}) - min({sze[pos], ret, n - sze[pos] - ret}));
    }
    for (auto j : adj[pos]) if (j != par) dfs2(j, pos);
    x.insert(sze[pos]);
}
bool check (int x, int y) {
    return in[x] <= in[y] && in[y] <= out[x];
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1, -1);
    dfs2(1, -1);
    cout << mn << '\n';
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16732 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16744 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 5 ms 16840 KB Output is correct
8 Correct 5 ms 16732 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 6 ms 16968 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16732 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 4 ms 16744 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 5 ms 16840 KB Output is correct
8 Correct 5 ms 16732 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 6 ms 16968 KB Output is correct
11 Correct 120 ms 25844 KB Output is correct
12 Correct 191 ms 25992 KB Output is correct
13 Correct 129 ms 26188 KB Output is correct
14 Correct 123 ms 25940 KB Output is correct
15 Correct 159 ms 25820 KB Output is correct
16 Correct 94 ms 25552 KB Output is correct
17 Correct 114 ms 25940 KB Output is correct
18 Execution timed out 1053 ms 34640 KB Time limit exceeded
19 Halted 0 ms 0 KB -