제출 #851425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851425		vjudge1	Papričice (COCI20_papricice)	C++17	0 / 110	58 ms	8532 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];

void solve() {
    memset(ok, true, sizeof(ok));

    int n; 
    cin >> n;

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

        if(edges[i].first > edges[i].second) {
            swap(edges[i].first, edges[i].second);
        }

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

    function <int(int, int)> dfs = [&](int node, int par) -> int {
        //cerr << node << " " << par << "\n";
        int res = 1;
        for(int &child : adj[node]) {
            if(child != par && ok[child][node]) {
                res += dfs(child, node);
            }
        }

        return res;
    };

    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];

            ok[a][b] = ok[b][a] = false;
            ok[c][d] = ok[d][c] = false;

            vector <int> sizes;
            sizes.emplace_back(dfs(a, 0));
            sizes.emplace_back(dfs(b, 0));
            sizes.emplace_back(dfs(c, 0));
            sizes.emplace_back(dfs(d, 0));

            sort(sizes.begin(), sizes.end());
            sizes.erase(unique(sizes.begin(), sizes.end()), sizes.end());

            if(sizes.size() == 1) {
                sizes.emplace_back(sizes.front());
            }

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

            ok[a][b] = ok[b][a] = true;
            ok[c][d] = ok[d][c] = true;

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