oj.uz

Submission #318340

# Submission time Handle Problem Language Result Execution time Memory
318340 2020-11-01T10:32:50 Z nkft Papričice (COCI20_papricice) C++17
110 / 110
 358 ms 29412 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define nbits(x) __builtin_popcount(x)
#define gcd(x, y) __gcd(x, y)
#define SYNC_OFF ios::sync_with_stdio(0); cin.tie(0);
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;  
const int MOD = 1e9 + 7; // 998244353;
const int N = 200100;
const int INF = 1e15; // 1e18;
const double PI = acos(-1);
const int dx[] = {-1,0,1,0,-1,1,1,-1};
const int dy[] = {0,1,0,-1,1,1,-1,-1};
int powmod(int a, int b, int m = MOD) {
    int res = 1;
    a %= m; assert(b >= 0);
    for (; b; b>>=1) {
        if (b & 1) res = res*a % m;
        a = a*a % m;
    }
    return res;
}

int n;
int sz[N];
vector<int> g[N];
multiset<int> A, B;

int dfs(int x, int p) {
    sz[x] = 1;
    for (int y: g[x]) {
        if (y != p) {
            sz[x] += dfs(y, x);
        }
    }
    return sz[x];
}

vector<int> cand(multiset<int>& S, int k) {
    vector<int> res;
    auto ub = S.upper_bound(k);
    if (ub != S.end()) {
        res.pb(*ub);
    }
    auto lb = S.lower_bound(k);
    if (lb != S.end()) {
        res.pb(*lb);
    }
    if (lb != S.begin()) {
        res.pb(*prev(lb));
    }
    return res;
}

int solve(int x, int p) {
    int ans = INF;
    for (int szy: cand(A, (n + sz[x]) / 2)) {
        int res = max({sz[x], szy - sz[x], n - szy});
        res -= min({sz[x], szy - sz[x], n - szy});
        ans = min(ans, res);
    }
    for (int szy: cand(B, (n - sz[x]) / 2)) {
        int res = max({sz[x], szy, n - sz[x] - szy});
        res -= min({sz[x], szy, n - sz[x] - szy});
        ans = min(ans, res);
    }
    A.insert(sz[x]);
    for (int y: g[x]) {
        if (y != p) {
            ans = min(ans, solve(y, x));
        }
    }
    A.erase(A.find(sz[x]));
    B.insert(sz[x]);
    return ans;
}

signed main() {
    SYNC_OFF;
    cin >> n;
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        g[u].pb(v); g[v].pb(u);
    }
    dfs(1, 0);
    cout << solve(1, 0) << "\n";
    return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 6 ms 5228 KB Output is correct
8 Correct 5 ms 5228 KB Output is correct
9 Correct 6 ms 5228 KB Output is correct
10 Correct 5 ms 5228 KB Output is correct
11 Correct 333 ms 23524 KB Output is correct
12 Correct 358 ms 23480 KB Output is correct
13 Correct 284 ms 24292 KB Output is correct
14 Correct 309 ms 23780 KB Output is correct
15 Correct 357 ms 23524 KB Output is correct
16 Correct 264 ms 24016 KB Output is correct
17 Correct 324 ms 23524 KB Output is correct
18 Correct 319 ms 29412 KB Output is correct
19 Correct 319 ms 23908 KB Output is correct
20 Correct 332 ms 23524 KB Output is correct