oj.uz

Submission #646798

# Submission time Handle Problem Language Result Execution time Memory
646798 2022-09-30T17:15:17 Z BackNoob Papričice (COCI20_papricice) C++14
110 / 110
 264 ms 37328 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
 
int n;
int sub[mxN];
vector<int> adj[mxN];
multiset<int> ms1;
multiset<int> ms2;
int res = inf;

void dfs_pre(int u, int p)
{
    sub[u] = 1;
    for(int v : adj[u]) {
        if(v == p) continue;
        dfs_pre(v, u);
        sub[u] += sub[v];
    }
}

void dfs(int u, int p)
{
    if(sz(ms1) > 0) {
        for(int d = -1; d <= 1; d++) {
            int x = (sub[u] + n + d) / 2;
            auto it = ms1.lower_bound(x);
            if(it != ms1.end()) {
                minimize(res, max({sub[u], *it - sub[u], n - *it}) - min({sub[u], *it - sub[u], n - *it}));
            }
            if(it != ms1.begin()) {
                --it;
                minimize(res, max({sub[u], *it - sub[u], n - *it}) - min({sub[u], *it - sub[u], n - *it}));            
            }
        }
    }
    if(sz(ms2) > 0) {
        for(int d = -1; d <= 1; d++) {
            int x = (n - sub[u] + d) / 2;
            auto it = ms2.lower_bound(x);
            if(it != ms2.end()) {
                minimize(res, max({sub[u], *it , n - *it - sub[u]}) - min({sub[u], *it, n - *it - sub[u]}));
            }
            if(it != ms2.begin()) {
                --it;
                minimize(res, max({sub[u], *it , n - *it - sub[u]}) - min({sub[u], *it, n - *it - sub[u]}));
            }
        }
    }

    ms1.insert(sub[u]);
    for(int v : adj[u]) {
        if(v == p) continue;
        dfs(v, u);
    }

    ms1.erase(ms1.find(sub[u]));
    ms2.insert(sub[u]);
}

void solve()
{
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dfs_pre(1, -1);
    dfs(1, -1);

    cout << res;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

 
    int tc = 1;
    //cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12080 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12008 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12080 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12008 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 12244 KB Output is correct
7 Correct 8 ms 12220 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 7 ms 12244 KB Output is correct
10 Correct 8 ms 12264 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12080 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12008 KB Output is correct
5 Correct 7 ms 11988 KB Output is correct
6 Correct 7 ms 12244 KB Output is correct
7 Correct 8 ms 12220 KB Output is correct
8 Correct 7 ms 12244 KB Output is correct
9 Correct 7 ms 12244 KB Output is correct
10 Correct 8 ms 12264 KB Output is correct
11 Correct 233 ms 31024 KB Output is correct
12 Correct 242 ms 31044 KB Output is correct
13 Correct 198 ms 31448 KB Output is correct
14 Correct 207 ms 31228 KB Output is correct
15 Correct 236 ms 30972 KB Output is correct
16 Correct 208 ms 31120 KB Output is correct
17 Correct 218 ms 31172 KB Output is correct
18 Correct 264 ms 37328 KB Output is correct
19 Correct 211 ms 31256 KB Output is correct
20 Correct 250 ms 31036 KB Output is correct