Submission #1100908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100908		BuiDucManh123	Meetings 2 (JOI21_meetings2)	C++14	0 / 100	2 ms	11004 KiB

meetings2

#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 (stderr)

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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80