Submission #390114

#	Time	Username	Problem	Language	Result	Execution time	Memory
390114		apostoldaniel854	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	1067 ms	32300 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"

const int MAX_N = 2e5;
int n;
vector <int> graph[1 + MAX_N];
int sz[1 + MAX_N];
int sol[1 + MAX_N];
bool used[1 + MAX_N];
int h[1 + MAX_N];
int best_depth[1 + MAX_N];

void upd (int &a, int b) {
    if (a < b)
        a = b;
}

void dfs_sz (int node, int par) {
    sz[node] = 1;
    for (int son : graph[node])
        if (son != par && not used[son]) {
            dfs_sz (son, node);
            sz[node] += sz[son];
        }
}


int get_centroid (int node, int par, int target) {
    for (int son : graph[node])
        if (son != par && not used[son] && sz[son] > target)
            return get_centroid (son, node, target);
    return node;
}


struct node_t {
    int sz;
    int h;
    int id;
    bool operator < (const node_t &other) const {
        return sz < other.sz;
    }
};

vector <node_t> v;

void dfs_prec (int node, int par, int depth, int nr) {
    sz[node] = 1;
    h[node] = depth;
    for (int son : graph[node])
        if (son != par && not used[son]) {
            dfs_prec (son, node, depth + 1, nr);
            sz[node] += sz[son];
        }
    v.push_back ({sz[node], h[node], nr});
}

void solve (int node) { /// centroid :)
    dfs_sz (node, 0);
    int centroid = get_centroid (node, 0, sz[node] / 2);
    v.clear ();
    int nr = 0;
    for (int son : graph[centroid])
        if (not used[son]) {
            nr++;
            dfs_prec (son, centroid, 1, nr);
        }
    for (int i = 0; i <= nr; i++)
        best_depth[i] = 0;
    best_depth[0] = 0;;
    multiset <int> max_depths;
    max_depths.insert (0);
    sort (v.begin (), v.end ());
    reverse (v.begin (), v.end ());
    int min_sz = 0;
 //   dbg (centroid);
    for (node_t node : v) {
       // dbg (node.sz); dbg (node.h); dbg (node.id);
        min_sz = node.sz;
        if (best_depth[node.id] < node.h) {
            if (best_depth[node.id] > 0)
                max_depths.erase (max_depths.find (best_depth[node.id]));
            max_depths.insert (node.h);
            best_depth[node.id] = node.h;
        }
        if (max_depths.size () > 1) {
            auto it = max_depths.end ();
            it = prev (it);
            int dist1 = *it;
            it = prev (it);
            int dist2 = *it;
          //  dbg (dist1); dbg (dist2);
            sol[min_sz * 2] = max (sol[min_sz * 2], dist1 + dist2 + 1);
        }
    }

    used[centroid] = true;
    for (int vec : graph[centroid])
        if (not used[vec])
            solve (vec);
}
/**
5
1 2
2 3
4 2
3 5
**/
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n;
    for (int i = 1; i < n; i++) {
        register int x, y;
        cin >> x >> y;
        graph[x].push_back (y);
        graph[y].push_back (x);
    }
    if (n == 2) {
        cout << "1\n2\n";
        return 0;
    }
    for (int i = 1; i <= n; i++)
        sol[i] = 1;
    solve (1);
    for (int i = n - 2; i > 0; i--)
        sol[i] = max (sol[i], sol[i + 2]);
    for (int i = 1; i <= n; i++)
        cout << sol[i] << "\n";
    return 0;
}

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