Submission #1032274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032274		tvladm2009	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	484 ms	33472 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(a) (a).begin(), (a).end()

const int N = 2e5 + 5;

int n;
vector<int> g[N];
int init_sz[N], init_d[N];
bool used[N];
int sz[N], d[N], ans[N], first[N];

void build(int u, int p = -1, int cd = 0) {
    init_sz[u] = 1;
    init_d[u] = cd;
    for (auto v : g[u]) {
        if (v != p) {
            build(v, u, cd + 1);
            init_sz[u] += init_sz[v];
        }
    }
}

int get_subtree_sz(int u, int v) {
    return init_d[u] < init_d[v] ? init_sz[v] : n - init_sz[u];
}

void dfs(int u, int p = -1, int cd = 0) {
    sz[u] = 1;
    d[u] = cd;
    for (auto v : g[u]) {
        if (!used[v] && v != p) {
            dfs(v, u, cd + 1);
            sz[u] += sz[v];
        }
    }
}

int fcen(int all_sz, int u, int p = -1) {
    for (auto v : g[u]) {
        if (!used[v] && v != p && 2 * sz[v] > all_sz) {
            return fcen(all_sz, v, u);
        }
    }
    return u;
}

void dfs_ans(int root, vector<pair<int, int>> &vs, int u, int p = -1) {
    if (u != root) {
        first[u] = p == root ? u : first[p];
        vs.push_back({get_subtree_sz(p, u), u});
        ans[2 * min(get_subtree_sz(p, u), get_subtree_sz(first[u], root))] = max(ans[2 * min(get_subtree_sz(p, u), get_subtree_sz(first[u], root))], d[u] + 1);
    }
    for (auto v : g[u]) {
        if (!used[v] && v != p) {
            dfs_ans(root, vs, v, u);
        }
    }
}

void solve(int root) {
    dfs(root);
    vector<pair<int, int>> vs;
    dfs_ans(root, vs, root);
    sort(all(vs));
    reverse(all(vs));
    vector<pair<int, int>> cur;
    for (auto [s, v] : vs) {
        for (auto [du, fu] : cur) {
            if (fu != first[v]) {
                ans[2 * s] = max(ans[2 * s], du + d[v] + 1);
            }
        }
        cur.push_back({d[v], first[v]});
        sort(all(cur));
        bool cont = true;
        for (int i = 0; i < cur.size() && cont; ++i) {
            for (int j = i + 1; j < cur.size() && cont; ++j) {
                if (cur[i].second == cur[j].second) {
                    cur.erase(cur.begin() + i);
                    cont = false;
                }
            }
        }
        if (cur.size() == 3) {
            cur.erase(cur.begin());
        }
    }
    used[root] = true;
    for (auto v : g[root]) {
        if (!used[v]) {
            solve(fcen(sz[v], v));
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i) {
        ans[i] = 1;
    }
    build(0);
    dfs(0);
    solve(fcen(n, 0));
    for (int i = n - 2; i >= 0; --i) {
        ans[i] = max(ans[i], ans[i + 2]);
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

meetings2.cpp: In function 'void solve(int)':
meetings2.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int i = 0; i < cur.size() && cont; ++i) {
      |                         ~~^~~~~~~~~~~~
meetings2.cpp:82:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for (int j = i + 1; j < cur.size() && cont; ++j) {
      |                                 ~~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80