oj.uz

Submission #851429

# Submission time Handle Problem Language Result Execution time Memory
851429 2023-09-19T18:14:33 Z vjudge1 Papričice (COCI20_papricice) C++17
15 / 110
 1000 ms 4696 KB 
//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);
    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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4184 KB Output is correct
2 Correct 59 ms 4188 KB Output is correct
3 Correct 55 ms 4188 KB Output is correct
4 Correct 53 ms 4184 KB Output is correct
5 Correct 55 ms 4440 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4184 KB Output is correct
2 Correct 59 ms 4188 KB Output is correct
3 Correct 55 ms 4188 KB Output is correct
4 Correct 53 ms 4184 KB Output is correct
5 Correct 55 ms 4440 KB Output is correct
6 Execution timed out 1039 ms 4696 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4184 KB Output is correct
2 Correct 59 ms 4188 KB Output is correct
3 Correct 55 ms 4188 KB Output is correct
4 Correct 53 ms 4184 KB Output is correct
5 Correct 55 ms 4440 KB Output is correct
6 Execution timed out 1039 ms 4696 KB Time limit exceeded
7 Halted 0 ms 0 KB -