oj.uz

Submission #366447

# Submission time Handle Problem Language Result Execution time Memory
366447 2021-02-14T08:17:29 Z NONAME Papričice (COCI20_papricice) C++14
110 / 110
 550 ms 86840 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
using namespace std;

const int man = (int)(2e5 + 500);

int n, ans;
int nt[man], sz[man];
vector <int> g[man];
set <pair <int, int> > s[man];

void upd(int f1, int f2, int f3) {
    // cerr << f1 << " " << f2 << " " << f3 << "\n";
    if (ans == -1) {
        ans = max(max(f1, f2), f3) - min(min(f1, f2), f3);
    }
    ans = min(ans, max(max(f1, f2), f3) - min(min(f1, f2), f3));
}

void link(int v, int u) {
    int pv = nt[v], pu = nt[u];
    // bool gd = false;
    // if ((v == 2) && (u == 4)) {
    //     cerr << "! " << pv << " " << pu << " -> ";
    //     for (auto& i : s[pu]) {
    //         cerr << (i.second + 1) << " ";
    //     }
    //     cerr << "\n";
    //     gd = true;
    // }

    if ((int)(s[pv].size()) < (int)(s[pu].size())) {
        swap(pv, pu);
        swap(v, u);
    }

    // if (gd == true) {
    //     cerr << (v + 1) << " " << (u + 1) << " " << pv << " " << pu << "\n";
    // }

    for (auto& i : s[pu]) {
        int ost = n - i.first;
        int f1 = i.first, f2, f3;
        auto it = s[pv].upper_bound({ost / 2, -1});
        int cnt = 0;
        while ((cnt < 2) && (it != s[pv].begin())) {
            ++cnt;
            --it;
        }

        cnt = 0;
        while ((cnt < 4) && (it != s[pv].end())) {
            f2 = (*it).first;
            f3 = ost - (*it).first;
            
            upd(f1, f2, f3);
            ++cnt;
            ++it;
        }
    }

    for (auto& i : s[pu]) {
        nt[i.second] = pv;
        s[pv].insert(i);
    }

    nt[u] = nt[pu] = pv;
}

void dfs(int v, int pr) {
    sz[v] = 1;
    for (auto& u : g[v]) {
        if (u == pr) {
            continue;
        }

        dfs(u, v);
        sz[v] += sz[u];
        link(v, u);
    }

    if ((s[nt[v]].empty() == false) && (v != 0)) {
        int f1 = n - sz[v], f2, f3;
        int ost = sz[v];
        auto it = s[nt[v]].upper_bound({ost / 2, -1});
        int cnt = 0;
        while ((cnt < 2) && (it != s[nt[v]].begin())) {
            ++cnt;
            --it;
        }

        cnt = 0;
        while ((cnt < 4) && (it != s[nt[v]].end())) {
            // cerr << "! " << (v + 1) << " " << (*it).first << " " << ((*it).second + 1) << "\n";
            f2 = (*it).first;
            f3 = ost - (*it).first;
            
            upd(f1, f2, f3);
            // cerr << "\n";
            ++cnt;
            ++it;
        }
    }

    s[nt[v]].insert({sz[v], v});

    // cerr << (v + 1) << " " << nt[v] << "\n";
    // for (auto& i : s[nt[v]]) {
    //     cerr << (i.second + 1) << " ";
    // }
    // cerr << "\n";
    // cerr << "\n";
}

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

    #ifdef _LOCAL
        in("inD.txt");
        out("outD.txt");
    #endif

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

        g[v].push_back(u);
        g[u].push_back(v);
    }
    
    ans = -1;
    dfs(0, -1);

    cout << ans << "\n";

    return 0;
}

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 14444 KB Output is correct
4 Correct 11 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 14444 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 13 ms 14956 KB Output is correct
7 Correct 13 ms 14956 KB Output is correct
8 Correct 12 ms 14956 KB Output is correct
9 Correct 12 ms 14956 KB Output is correct
10 Correct 13 ms 14956 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 14444 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 13 ms 14956 KB Output is correct
7 Correct 13 ms 14956 KB Output is correct
8 Correct 12 ms 14956 KB Output is correct
9 Correct 12 ms 14956 KB Output is correct
10 Correct 13 ms 14956 KB Output is correct
11 Correct 550 ms 78444 KB Output is correct
12 Correct 507 ms 77676 KB Output is correct
13 Correct 494 ms 71916 KB Output is correct
14 Correct 508 ms 79980 KB Output is correct
15 Correct 527 ms 81516 KB Output is correct
16 Correct 364 ms 49896 KB Output is correct
17 Correct 488 ms 74348 KB Output is correct
18 Correct 280 ms 48620 KB Output is correct
19 Correct 522 ms 86840 KB Output is correct
20 Correct 472 ms 74056 KB Output is correct