oj.uz

Submission #564192

# Submission time Handle Problem Language Result Execution time Memory
564192 2022-05-18T17:25:20 Z nikatamliani Meetings 2 (JOI21_meetings2) C++14
0 / 100
 4 ms 5004 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> g[N];
int n, sub[N], done[N], f[N], ans[N];
int maxi;
int upper;
void add(int x, int y) {
    x = upper - x + 1;
    assert(x > 0);
    while (x <= upper) {
        f[x] = max(f[x], y);
        x += x & -x;
    }
}
int get(int x) {
    int ans = -N;
    x = upper - x + 1;
    while (x > 0) {
        ans = max(ans, f[x]);
        x -= x & -x;
    }
    return ans;
}
int find_centroid(int x, int p, int sz) {
    for (int to : g[x]) {
        if (!done[to] && to != p && sub[to] > sz / 2) {
            return find_centroid(to, x, sz);
        }
    }
    return x;
}
void calc(int x, int p) {
    sub[x] = 1;
    for (int to : g[x]) {
        if (!done[to] && p != to) {
            calc(to, x);
            sub[x] += sub[to];
        }
    }
}
void insert(int x, int p, int pos, int depth = 1) {
    for (int to : g[x]) {
        if (to != p && !done[to]) {
            insert(to, x, pos, depth + 1);
        }
    }
    if (pos == 1) {
        add(sub[x], depth);
    } else {
        ans[sub[x]] = max(ans[sub[x]], depth + get(sub[x]) + 1);
    }
}
void decomp(int x, int p, int sz) {
    calc(x, p);
    int c = find_centroid(x, -1, sz);
    upper = sz;
    calc(c, p);
    for (int i = 1; i <= sz; ++i) {
        f[i] = -1e9;
    }
    add(sub[c], 0);
    for (int to : g[c]) {
        if (done[to]) continue;
        insert(to, c, 0); 
        insert(to, c, 1);
    }
    for (int i = 1; i <= sz; ++i) {
        f[i] = -1e9;
    }
    add(sub[c], 0);
    reverse(g[c].begin(), g[c].end());
    for (int to : g[c]) {
        if (done[to]) continue;
        insert(to, c, 0);
        insert(to, c, 1);
    }
    for (int i = 1; i <= sz; ++i) {
        f[i] = -1e9;
    }
    done[c] = 1;
    for (int to : g[c]) {
        if (!done[to]) {
            decomp(to, c, sub[to]);
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    decomp(1, 0, n);
    for (int i = n; i >= 1; --i) {
        ans[i] = max(ans[i], ans[i + 1]);
    }
    for (int i = 1; i <= n; ++i) {
        if (i % 2 == 0) {
            cout << ans[i / 2] << '\n';
        } else {
            cout << "1\n";
        }
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Incorrect 3 ms 5000 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Incorrect 3 ms 5000 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5004 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Incorrect 3 ms 5000 KB Output isn't correct
6 Halted 0 ms 0 KB -