Submission #1311677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311677		giatri1904	Papričice (COCI20_papricice)	C++20	50 / 110	12 ms	580 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int n;
vector<int> adj[MAXN];
int parent[MAXN], sz[MAXN];
int tin[MAXN], tout[MAXN], timer;
void dfs(int u, int p) {
    parent[u] = p;
    sz[u] = 1;
    tin[u] = ++timer;

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }

    tout[u] = timer;
}
bool ok(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("a.inp","r",stdin);
    //freopen("a.out","w",stdout);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1, 0);
    int ans = n;
    for (int u = 2; u <= n; u++) {
        for (int v = u + 1; v <= n; v++) {
            int a, b, c;
            if (ok(u, v)) {
                a = sz[v];
                b = sz[u] - sz[v];
                c = n - sz[u];
            }
            else if (ok(v, u)) {
                a = sz[u];
                b = sz[v] - sz[u];
                c = n - sz[v];
            }
            else {
                a = sz[u];
                b = sz[v];
                c = n - sz[u] - sz[v];
            }

            int mx = max({a, b, c});
            int mn = min({a, b, c});
            ans = min(ans, mx - mn);
        }
    }
    cout << ans << "\n";
}

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