Submission #851433

#	Time	Username	Problem	Language	Result	Execution time	Memory
851433		vjudge1	Papričice (COCI20_papricice)	C++17	50 / 110	62 ms	29520 KiB

papricice

//author:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

#define ONLINE_JUDGE
const int MAXN = 2000 + 5;

bool ok[MAXN][MAXN];

ostream& operator<< (ostream& out, vector <int> &vec) {
    for(auto &i : vec)
        out << i << " ";
    return out;
}

void solve() {
    int n; 
    cin >> n;

    vector <int> adj[n +1];
    vector <pair <int, int>> edges(n);
    for(int i = 1; i <= n -1; i++) {
        cin >> edges[i].first >> edges[i].second;

        adj[edges[i].first].emplace_back(edges[i].second);
        adj[edges[i].second].emplace_back(edges[i].first);
    }

    vector <int> sizes(n +1), depths(n +1);
    vector <int> vec;
    function <int(int, int)> dfs = [&](int node, int par) -> int {
        //cerr << node << " " << par << "\n";
        depths[node] = depths[par] +1;

        vec.emplace_back(node);

        int res = 1;
        for(int &child : adj[node]) {
            if(child != par) {
                res += dfs(child, node);
            }
        }

        for(int &i : vec) 
            ok[i][node] = ok[node][i] = true;

        //cerr << "vec: " << vec << "\n";

        vec.pop_back();

        return sizes[node] = res;
    };

    dfs(1, 0);

    for(int i = 1; i <= n -1; i++) {
        auto &[a, b] = edges[i];
        if(depths[a] < depths[b]) {
            swap(a, b);
        }
    }

    int ans = n;
    for(int i = 1; i <= n -1; i++) {
        for(int j = i +1; j <= n -1; j++) {
            auto [a, b] = edges[i];
            auto [c, d] = edges[j];

            int sz1 = sizes[0];
            int sz2 = sizes[1];
            int sz3 = n - (sizes[0] + sizes[1]);

            if(ok[a][c]) {
                if(depths[a] < depths[c]) 
                    swap(a, c);
                
                sz1 = sizes[a];
                sz2 = (sizes[c] - sizes[a]);
                sz3 = n - (sz1 + sz2);
            } else {
                sz1 = sizes[a];
                sz2 = sizes[c];
                sz3 = n - (sz1 + sz2);
            }

            //cerr << a << " " << b << " :: " << c << " " << d << " -> ";
            //cerr << sz1 << " " << sz2 << " " << sz3 << "\n";

            ans = min(ans, max({sz1, sz2, sz3}) - min({sz1, sz2, sz3}));
        }
    }

    cout << ans;
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    while(t--)
        solve();

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60