oj.uz

Submission #896112

# Submission time Handle Problem Language Result Execution time Memory
896112 2023-12-31T20:06:42 Z juliany2 Meetings 2 (JOI21_meetings2) C++17
0 / 100
 4 ms 12376 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 2e5 + 7;
int n;
vector<int> adj[N], s[N];
bool col[N];
int sz[N], dist[N], bst;
int ans[N];

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

    s[sz[v]].push_back(v);
}

void calc(int v = 1, int p = 0) {
    if (col[v]) {
        dist[v] = max(dist[v], 0);
        bst = max(bst, dist[v] + 1);
    }

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

int upd(int s) {
    col[s] = 1;
    memset(dist, -1, sizeof(dist));

    int ret = 0;

    queue<int> q;
    q.push(s);
    dist[s] = 0;

    while (q.size()) {
        int v = q.front();
        q.pop();

        if (col[v])
            ret = max(ret, dist[v] + 1);

        for (int u : adj[v]) {
            if (dist[u] < 0) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }

    return ret;
}

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);
    }

    dfs();

    for (int i = n; i >= 1; i--) {
        if (i % 2)
            ans[i] = 1;
        else {
            for (int x : s[i / 2])
                ans[i] = max(ans[i], upd(x));
            for (int x : s[n - i / 2])
                ans[i] = max(ans[i], upd(x));

            fill(dist + 1, dist + n + 1, (int) -1e9);
            bst = 0;
            calc();

            ans[i] = max(ans[i], bst + 1);
        }
    }

    for (int i = 1; i <= n; i++)
        cout << ans[i] << '\n';

    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 3 ms 12376 KB Output is correct
3 Correct 3 ms 12120 KB Output is correct
4 Correct 3 ms 12216 KB Output is correct
5 Correct 3 ms 12120 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 4 ms 12216 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 3 ms 12124 KB Output is correct
10 Correct 3 ms 12124 KB Output is correct
11 Correct 3 ms 12124 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Incorrect 3 ms 12124 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 3 ms 12376 KB Output is correct
3 Correct 3 ms 12120 KB Output is correct
4 Correct 3 ms 12216 KB Output is correct
5 Correct 3 ms 12120 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 4 ms 12216 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 3 ms 12124 KB Output is correct
10 Correct 3 ms 12124 KB Output is correct
11 Correct 3 ms 12124 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Incorrect 3 ms 12124 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 3 ms 12376 KB Output is correct
3 Correct 3 ms 12120 KB Output is correct
4 Correct 3 ms 12216 KB Output is correct
5 Correct 3 ms 12120 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 4 ms 12216 KB Output is correct
8 Correct 3 ms 12124 KB Output is correct
9 Correct 3 ms 12124 KB Output is correct
10 Correct 3 ms 12124 KB Output is correct
11 Correct 3 ms 12124 KB Output is correct
12 Correct 4 ms 12124 KB Output is correct
13 Incorrect 3 ms 12124 KB Output isn't correct
14 Halted 0 ms 0 KB -