oj.uz

Submission #851433

# Submission time Handle Problem Language Result Execution time Memory
851433 2023-09-19T18:29:58 Z vjudge1 Papričice (COCI20_papricice) C++17
50 / 110
 62 ms 29520 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];

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 7 ms 4440 KB Output is correct
7 Correct 8 ms 4440 KB Output is correct
8 Correct 8 ms 4440 KB Output is correct
9 Correct 8 ms 4444 KB Output is correct
10 Correct 7 ms 4444 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 7 ms 4440 KB Output is correct
7 Correct 8 ms 4440 KB Output is correct
8 Correct 8 ms 4440 KB Output is correct
9 Correct 8 ms 4444 KB Output is correct
10 Correct 7 ms 4444 KB Output is correct
11 Runtime error 62 ms 29520 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -