Submission #895806

#	Time	Username	Problem	Language	Result	Execution time	Memory
895806		juliany2	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	1 ms	604 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 4007;
int n;
vector<int> adj[N];
int sz[N], dist[N];
int x, ans;

void prep(int v = 1, int p = 0) {
    sz[v] = 1;
    for (int u : adj[v]) {
        if (u != p) {
            prep(u, v);
            sz[v] += sz[u];
        }
    }
}

void dfs(int v = 1, int p = 0) {
    if (sz[v] >= x)
        dist[v] = 0;

    for (int u : adj[v]) {
        if (u != p) {
            dfs(u, v);
            dist[v] = max(dist[v], dist[u] + 1);
        }
    }

    if (n - sz[v] >= x)
        ans = max(ans, dist[v] + 2);
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    prep();

    for (int i = 1; i <= n; i++) {
        if (i % 2 == 1)
            cout << 1 << '\n';
        else {
            x = i / 2, ans = 1;
            for (int j = 1; j <= n; j++)
                dist[j] = -1e9;

            dfs();

            for (int j = 1; j <= n; j++) {
                if (sz[j] == x) {
                    vector<bool> vis(n + 1);
                    queue<array<int, 2>> q;
                    q.push({j, 0});
                    vis[j] = 1;

                    while (q.size()) {
                        auto [v, d] = q.front();
                        q.pop();

                        if (sz[v] == x)
                            ans = max(ans, d + 1);

                        for (int u : adj[v]) {
                            if (!vis[u]) {
                                vis[u] = 1;
                                q.push({u, d + 1});
                            }
                        }
                    }
                }
            }

            cout << ans << '\n';
        }
    }

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80