oj.uz

Submission #398171

# Submission time Handle Problem Language Result Execution time Memory
398171 2021-05-03T20:45:11 Z 4fecta Meetings 2 (JOI21_meetings2) C++17
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 4005;

int n, u, v, ans[MN], dep[MN], sz[MN], vis[MN], bit[MN]; //deepest dep with this size
vector<int> a[MN], upds;
pii ed[MN];

void upd(int x, int val) {
    for (int i = x; i < MN; i += i & -i) bit[i] = max(bit[i], val);
    upds.push_back(x);
}

int qry(int x) {
    int ret = 0;
    for (int i = x; i > 0; i -= i & -i) ret = max(ret, bit[i]);
    return ret;
}

void rev(int x) {
    for (int i = x; i < MN; i += i & -i) bit[i] = 0;
}

void reset() {
    //memset(bit, 0, sizeof(bit));
    while (upds.size()) rev(upds.back()), upds.pop_back();
}

int get_size(int cur, int pre) {
    sz[cur] = 1;
    for (int nxt : a[cur]) {
        if (vis[nxt] || nxt == pre) continue;
        sz[cur] += get_size(nxt, cur);
    }
    return sz[cur];
}

int get_cent(int cur, int pre, int siz) {
    for (int nxt : a[cur]) {
        if (vis[nxt] || nxt == pre) continue;
        if (sz[nxt] * 2 > siz) return get_cent(nxt, cur, siz);
    }
    return cur;
}

void dfs(int cur, int pre, int d) {
    dep[cur] = d;
    int md = qry(n - sz[cur] + 1);
    if (md) {
        //printf("%d %d %d\n", cur, sz[cur], d + md + 1);
        ans[sz[cur] * 2] = max(ans[sz[cur] * 2], d + md + 1);
    }
    for (int nxt : a[cur]) {
        if (vis[nxt] || nxt == pre) continue;
        dfs(nxt, cur, d + 1);
    }
}

void dfs(int cur, int pre) {
    //printf("upd: %d %d %d\n", cur, sz[cur], dep[cur]);
    upd(n - sz[cur] + 1, dep[cur]);
    for (int nxt : a[cur]) {
        if (vis[nxt] || nxt == pre) continue;
        dfs(nxt, cur);
    }
}

void dfs1(int cur, int pre) {
    sz[cur] = 1;
    for (int nxt : a[cur]) {
        if (nxt == pre) continue;
        dfs1(nxt, cur);
        sz[cur] += sz[nxt];
    }
}

void solve(int cur) {
    cur = get_cent(cur, cur, get_size(cur, cur));
    get_size(cur, cur);
    //printf("cur: %lld\n", cur);
    reset();
    for (int nxt : a[cur]) {
        dfs(nxt, cur, 1);
        dfs(nxt, cur);
    }
    reverse(a[cur].begin(), a[cur].end());
    reset();
    for (int nxt : a[cur]) {
        dfs(nxt, cur, 1);
        dfs(nxt, cur);
    }
    vis[cur] = 1;
    for (int nxt : a[cur]) {
        if (vis[nxt]) continue;
        //solve(nxt);
    }
}

int32_t main() {
    boost();

    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
        ed[i] = {u, v};
    }
    solve(1);
    dfs1(1, 0);
    for (int i = 2; i <= n; i++) {
        int csz = min(sz[i], n - sz[i]);
        ans[csz * 2] = max(ans[csz * 2], 2ll);
    }
    for (int i = n; i > 0; i--) ans[i] = max({1ll, ans[i + 1], ans[i]});
    for (int i = 1; i <= n; i++) printf("%lld\n", i % 2 ? 1 : ans[i]);

    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 80.0

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