oj.uz

답안 #1100908

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100908 2024-10-15T02:50:38 Z BuiDucManh123 Meetings 2 (JOI21_meetings2) C++14
0 / 100
 2 ms 11004 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define taskname ""
#define int ll

using namespace std;

ll sz[200009], ma[200009], pre[200009], i, m, n, u, v, ans[200009], check[200009], maxdepth;
vector<int> g[200009];

// DFS để tính kích thước các cây con
void dfs(int id, int par) {
    sz[id] = 1;
    for (int x : g[id]) {
        if (x == par || check[x]) continue;
        dfs(x, id);
        sz[id] += sz[x];
    }
}

// Tìm centroid của cây
int centroid(int id, int par, int siz) {
    for (int u : g[id]) {
        if (u == par || check[u]) continue;
        if (sz[u] * 2 >= siz) return centroid(u, id, siz);
    }
    return id;
}

// DFS để tính độ sâu và giá trị lớn nhất
void dfs2(int id, int par, int h) {
    maxdepth = max(maxdepth, sz[id]);  // Sửa lại từ sz[u] thành sz[id]
    ma[sz[id]] = max(ma[sz[id]], h);
    for (int u : g[id]) {
        if (u == par || check[u]) continue;
        dfs2(u, id, h + 1);
    }
}

// Xử lý từng centroid
void solve(int id) {
    // Bước 1: Tính kích thước cây con
    dfs(id, 0);
    int c = centroid(id, 0, sz[id]);  // Tìm centroid của cây
    check[c] = 1;  // Đánh dấu centroid là đã xử lý

    // Bước 2: Tính lại kích thước sau khi xác định centroid
    dfs(c, 0);

    // Bước 3: Tính toán giá trị lớn nhất dựa trên các cây con của centroid
    maxdepth = 0;
    for (int u : g[c]) {
        if (check[u]) continue;
        dfs2(u, c, 2);

        for (int i = sz[u] - 1; i >= 1; i--) ma[i] = max(ma[i], ma[i + 1]);

        for (int i = sz[u]; i >= 1; i--) {
            ans[i * 2] = max(ans[i * 2], ma[i]);
            ans[i * 2] = max(ans[i * 2], ma[i] + pre[i] - 1);
            pre[i] = max(pre[i], ma[i]);
        }

        // Đặt lại mảng `ma[]` sau mỗi cây con
        for (int i = 1; i <= sz[u]; i++) ma[i] = 0;
    }

    // Đặt lại các giá trị `pre[]` và `ma[]` sau khi tính toán cho các cây con
    for (int i = 1; i <= maxdepth; i++) pre[i] = 0, ma[i] = 0;

    // Bước 4: Xử lý đệ quy với các cây con của centroid
    for (int u : g[c]) {
        if (check[u]) continue;
        solve(u);
    }
}

signed main() {
    if (fopen(taskname ".inp", "r")) {
        freopen(taskname ".inp", "r", stdin);
        freopen(taskname ".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (i = 1; i < n; i++) {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    // Gọi hàm xử lý từ node 1
    solve(1);

    // In kết quả
    for (i = 1; i <= n; i++) {
        if (i & 1) cout << 1 << "\n";
        else cout << ans[i] << "\n";
    }

    return 0;
}

Compilation message

meetings2.cpp: In function 'int main()':
meetings2.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(taskname ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(taskname ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11004 KB Output is correct
2 Correct 2 ms 10832 KB Output is correct
3 Correct 2 ms 10832 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Incorrect 2 ms 10832 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11004 KB Output is correct
2 Correct 2 ms 10832 KB Output is correct
3 Correct 2 ms 10832 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Incorrect 2 ms 10832 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11004 KB Output is correct
2 Correct 2 ms 10832 KB Output is correct
3 Correct 2 ms 10832 KB Output is correct
4 Correct 2 ms 10832 KB Output is correct
5 Incorrect 2 ms 10832 KB Output isn't correct
6 Halted 0 ms 0 KB -