oj.uz

Submission #334054

# Submission time Handle Problem Language Result Execution time Memory
334054 2020-12-08T08:01:37 Z wiwiho Papričice (COCI20_papricice) C++14
110 / 110
 331 ms 29420 KB 
#include <bits/stdc++.h>

#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define eb emplace_back
#define printv(a, b) { \
    bool ps = false; \
    for(auto v : a){ \
        if(ps) b << " "; \
        b << v; ps = true; \
    } \
    b << "\n"; \
}
#define lsort(a) sort(iter(a))

using namespace std;

typedef long long ll;

const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

vector<vector<int>> g;
multiset<int> s1, s2;
vector<int> sz;
int ans = MAX;
int n;

void dfs(int now, int p){
    for(int i : g[now]){
        if(i == p) continue;
        dfs(i, now);
        sz[now] += sz[i];
    }
}

int diff(int a, int b, int c){
    return max({abs(a - b), abs(b - c), abs(a - c)});
}

void dfs2(int now, int p){
    int t = sz[now];
    auto it = s1.lower_bound((n - t) / 2);
    if(it != s1.end()) ans = min(ans, diff(t, *it, n - t - *it));
    if(it != s1.begin()) it--, ans = min(ans, diff(t, *it, n - t - *it));
    it = s2.lower_bound(t + (n - t) / 2);
    if(it != s2.end()) ans = min(ans, diff(t, *it - t, n - *it));
    if(it != s2.begin()) it--, ans = min(ans, diff(t, *it - t, n - *it));

    s2.insert(sz[now]);
    for(int i : g[now]){
        if(i != p) dfs2(i, now);
    }

    s2.erase(s2.find(sz[now]));
    s1.insert(sz[now]);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    g.resize(n + 1);
    sz.resize(n + 1, 1);

    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }

    dfs(1, 1);
    dfs2(1, 1);

    cout << ans << "\n";
    
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 300 ms 24088 KB Output is correct
12 Correct 329 ms 24172 KB Output is correct
13 Correct 248 ms 24556 KB Output is correct
14 Correct 284 ms 24300 KB Output is correct
15 Correct 313 ms 24044 KB Output is correct
16 Correct 194 ms 24088 KB Output is correct
17 Correct 284 ms 24172 KB Output is correct
18 Correct 290 ms 29420 KB Output is correct
19 Correct 267 ms 24300 KB Output is correct
20 Correct 331 ms 24044 KB Output is correct