oj.uz

Submission #366425

# Submission time Handle Problem Language Result Execution time Memory
366425 2021-02-14T07:26:33 Z kartel Papričice (COCI20_papricice) C++14
110 / 110
 266 ms 40684 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-10
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long double ld;
typedef unsigned long long ull;

const int N = 2e5 + 500;

set <int> vc[N];
int pr[N], siz[N], ans = 1e9;
vector <int> g[N];
int n;

int f(int v) { return (pr[v] == v ? v : pr[v] = f(pr[v])); }

void link(int v, int u) {
    v = f(v);
    u = f(u);

    if (sz(vc[v]) > sz(vc[u]))
        swap(u, v);

    set <int> :: iterator it = vc[u].begin();

    for (auto x : vc[v]) {
        set<int> ::iterator it = vc[u].lower_bound(x);

        if (it != vc[u].end()) {
            ans = min(ans, max({n - x - *it, *it, x}) - min({n - x - *it, *it, x}));
        }

        if (it != vc[u].begin()) {
            it--;
            ans = min(ans, max({n - x - *it, *it, x}) - min({n - x - *it, *it, x}));
            it++;
        }

        if (it != vc[u].end() && ++it != vc[u].end()) {
            ans = min(ans, max({n - x - *it, *it, x}) - min({n - x - *it, *it, x}));
        }
    }

    for (auto x : vc[v])
        vc[u].insert(x);

    pr[v] = u;
}

void dfs(int v, int pred) {
    siz[v] = 1;
    pr[v] = v;

    for (auto u : g[v]) {
        if (u == pred)
            continue;

        dfs(u, v);

        siz[v] += siz[u];
        int U = f(u);

        set<int> ::iterator it = vc[U].lower_bound(siz[u] / 2);

        ans = min(ans, max({n - siz[u], siz[u] - *it, *it}) - min({n - siz[u], siz[u] - *it, *it}));
        if (it != vc[U].begin()) {
            it--;
            ans = min(ans, max({n - siz[u], siz[u] - *it, *it}) - min({n - siz[u], siz[u] - *it, *it}));
            it++;
        }

        if (it != vc[U].end() && ++it != vc[U].end()) {

            ans = min(ans, max({n - siz[u], siz[u] - *it, *it}) - min({n - siz[u], siz[u] - *it, *it}));
        }

        link(u, v);
    }

    vc[f(v)].insert(siz[v]);
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//  in("pizza.in");
//  out("pizza.out");
//    in("input.txt");
////    out("output.txt");

    cin >> n;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, -1);

    cout << ans;
}

Compilation message

papricice.cpp: In function 'void link(int, int)':
papricice.cpp:45:27: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   45 |     set <int> :: iterator it = vc[u].begin();
      |                           ^~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 11 ms 14700 KB Output is correct
7 Correct 11 ms 14700 KB Output is correct
8 Correct 11 ms 14700 KB Output is correct
9 Correct 11 ms 14700 KB Output is correct
10 Correct 11 ms 14700 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 11 ms 14700 KB Output is correct
7 Correct 11 ms 14700 KB Output is correct
8 Correct 11 ms 14700 KB Output is correct
9 Correct 11 ms 14700 KB Output is correct
10 Correct 11 ms 14700 KB Output is correct
11 Correct 246 ms 33656 KB Output is correct
12 Correct 266 ms 36716 KB Output is correct
13 Correct 212 ms 35712 KB Output is correct
14 Correct 235 ms 36204 KB Output is correct
15 Correct 258 ms 36716 KB Output is correct
16 Correct 163 ms 34280 KB Output is correct
17 Correct 231 ms 36076 KB Output is correct
18 Correct 211 ms 40684 KB Output is correct
19 Correct 229 ms 36972 KB Output is correct
20 Correct 250 ms 37100 KB Output is correct