oj.uz

답안 #398176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398176 2021-05-03T21:04:07 Z 4fecta Meetings 2 (JOI21_meetings2) C++17
20 / 100
 9 ms 844 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], rsz; //deepest dep with this size
vector<int> a[MN], upds;

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) {
        //if (sz[cur] == 3) printf("%d %d %d\n", cur, sz[cur], d + md + 1);
        ans[sz[cur] * 2] = max(ans[sz[cur] * 2], d + md + 1);
    }
    ans[min(rsz, sz[cur]) * 2] = max(ans[min(rsz, sz[cur]) * 2], d + 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]) {
        if (vis[nxt]) continue;
        rsz = n - sz[nxt];
        dfs(nxt, cur, 1);
        dfs(nxt, cur);
    }
    reverse(a[cur].begin(), a[cur].end());
    reset();
    for (int nxt : a[cur]) {
        if (vis[nxt]) continue;
        rsz = n - sz[nxt];
        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);
    }
    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
4.0 / 4.0

# 결과 실행 시간 메모리 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 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 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 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 7 ms 716 KB Output is correct
23 Correct 7 ms 720 KB Output is correct
24 Correct 7 ms 716 KB Output is correct
25 Correct 8 ms 708 KB Output is correct
26 Correct 7 ms 716 KB Output is correct
27 Correct 6 ms 768 KB Output is correct
28 Correct 7 ms 716 KB Output is correct
29 Correct 6 ms 716 KB Output is correct
30 Correct 6 ms 716 KB Output is correct
31 Correct 7 ms 716 KB Output is correct
32 Correct 9 ms 844 KB Output is correct
33 Correct 8 ms 844 KB Output is correct
34 Correct 3 ms 716 KB Output is correct
35 Correct 3 ms 716 KB Output is correct
36 Correct 7 ms 816 KB Output is correct
37 Correct 3 ms 716 KB Output is correct
38 Correct 6 ms 816 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 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 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 7 ms 716 KB Output is correct
23 Correct 7 ms 720 KB Output is correct
24 Correct 7 ms 716 KB Output is correct
25 Correct 8 ms 708 KB Output is correct
26 Correct 7 ms 716 KB Output is correct
27 Correct 6 ms 768 KB Output is correct
28 Correct 7 ms 716 KB Output is correct
29 Correct 6 ms 716 KB Output is correct
30 Correct 6 ms 716 KB Output is correct
31 Correct 7 ms 716 KB Output is correct
32 Correct 9 ms 844 KB Output is correct
33 Correct 8 ms 844 KB Output is correct
34 Correct 3 ms 716 KB Output is correct
35 Correct 3 ms 716 KB Output is correct
36 Correct 7 ms 816 KB Output is correct
37 Correct 3 ms 716 KB Output is correct
38 Correct 6 ms 816 KB Output is correct
39 Runtime error 1 ms 588 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -