Submission #1026629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026629		adaawf	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	530 ms	54380 KiB

meetings2

#include <iostream>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
int s[200005], l[200005][19], d[200005], c[200005], dd[200005], da[200005], z = 0, ff[200005];
vector<int> g[200005];
vector<pair<int, int>> gg[200005];
set<int> t;
void dfs(int x, int p) {
    s[x] = 1;
    dd[x] = ++z;
    l[x][0] = p;
    for (int w : g[x]) {
        if (w == p) continue;
        c[x]++;
        d[w] = d[x] + 1;
        dfs(w, x);
        s[x] += s[w];
    }
    if (p != 0 && g[x].size() == 1) t.insert(x);
    da[x] = z;
}
int lca(int x, int y) {
    if (d[x] < d[y]) swap(x, y);
    int k = d[x] - d[y];
    for (int i = 18; i >= 0; i--) {
        if (k & (1 << i)) {
            x = l[x][i];
        }
    }
    if (x == y) return x;
    for (int i = 18; i >= 0; i--) {
        if (l[x][i] != l[y][i]) {
            x = l[x][i];
            y = l[y][i];
        }
    }
    return l[x][0];
}
bool cmp(int x, int y) {
    return dd[x] < dd[y];
}
int ma = 1;
void dfs2(int x, int p) {
    ff[x] = 0;
    for (auto w : gg[x]) {
        if (w.first == p) continue;
        //cout << x << " " << w.first << " " << w.second << '\n';
        dfs2(w.first, x);
        ma = max(ma, ff[w.first] + ff[x] + w.second + 1);
        ff[x] = max(ff[x], ff[w.first] + w.second);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= 18; i++) {
        for (int j = 1; j <= n; j++) {
            l[j][i] = l[l[j][i - 1]][i - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i & 1) {
            cout << 1 << '\n';
            continue;
        }
        vector<int> v, vb, vv, va;
        ma = 1;
        for (int w : t) {
            if (n - s[w] < i / 2) continue;
            int res = 0, k = w;
            for (int j = 18; j >= 0; j--) {
                if (l[k][j] == 0) continue;
                if (n - s[l[k][j]] >= i / 2) {
                    k = l[k][j];
                    res += (1 << j);
                }
            }
            ma = max(ma, res + 2);
        }
        for (int w : t) {
            v.push_back(w);
            vb.push_back(w);
        }
        sort(vb.begin(), vb.end(), cmp);
        for (int i = 1; i < vb.size(); i++) v.push_back(lca(vb[i], vb[i - 1]));
        sort(v.begin(), v.end(), cmp);
        int h = 0;
        stack<int> ss;
        for (int w : v) {
            if (w == h) continue;
            h = w;
            while (!ss.empty()) {
                int p = ss.top();
                if (dd[p] <= dd[w] && da[w] <= da[p]) {
                    gg[p].push_back({w, d[w] - d[p]});
                    break;
                }
                ss.pop();
            }
            ss.push(h);
        }
        while (ss.size() > 1) ss.pop();
        dfs2(ss.top(), -1);
        for (int w : vb) {
            if (s[w] == i / 2) {
                vv.push_back(w);
                c[l[w][0]]--;
                if (c[l[w][0]] == 0) va.push_back(l[w][0]);
            }
        }
        for (int w : v) gg[w].clear();
        for (int w : vv) t.erase(w);
        for (int w : va) t.insert(w);
        cout << ma << '\n';
    }
}

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (int i = 1; i < vb.size(); i++) v.push_back(lca(vb[i], vb[i - 1]));
      |                         ~~^~~~~~~~~~~

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