Submission #366447

#	Time	Username	Problem	Language	Result	Execution time	Memory
366447		NONAME	Papričice (COCI20_papricice)	C++14	110 / 110	550 ms	86840 KiB

papricice

#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 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60