Submission #564506

#	Time	Username	Problem	Language	Result	Execution time	Memory
564506		nikatamliani	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	1760 ms	34940 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> g[N], seen;
int n, c, sub[N], done[N], f[N], ans[N], par[N], exc[N];
int maxi;
int upper;
void add(int x, int y) {
    x = upper - x + 1;
    assert(x > 0);
    while (x <= upper) {
        seen.push_back(x);
        f[x] = max(f[x], y);
        x += x & -x;
    }
}
int get(int x) {
    int ans = -N;
    x = upper - x + 1;
    while (x > 0) {
        ans = max(ans, f[x]);
        x -= x & -x;
    }
    return ans;
}
int find_centroid(int x, int p, int sz) {
    for (int to : g[x]) {
        if (!done[to] && to != p && sub[to] > sz / 2) {
            return find_centroid(to, x, sz);
        }
    }
    return x;
}
void calc(int x, int p) {
    sub[x] = 1;
    for (int to : g[x]) {
        if (!done[to] && p != to) {
            calc(to, x);
            sub[x] += sub[to];
        }
    }
}
int excSize(int x, int dir) {
    if (par[x] == dir) {
        return exc[x];
    }
    return n - exc[dir]; 
}
void insert(int x, int p, int anc, int pos, int depth = 1) {
    for (int to : g[x]) {
        if (to != p && !done[to]) {
            insert(to, x, anc, pos, depth + 1);
        }
    }
    int sub_size = excSize(x, p);
    if (pos == 1) {
        add(sub_size, depth);
    } else {
        ans[sub_size] = max(ans[sub_size], depth + get(sub_size) + 1);
        int v = min(sub_size, excSize(c, anc));
        ans[v] = max(ans[v], depth + 1);
    }
}
void find_par(int x, int p) {
    par[x] = p;
    exc[x] = 1;
    for (int to : g[x]) {
        if (to != p) {
            find_par(to, x);
            exc[x] += exc[to];
        }
    }
}
void decomp(int x, int p, int sz) {
    calc(x, p);
    c = find_centroid(x, -1, sz);
    upper = n;
    calc(c, p);
    for (int to : g[c]) {
        if (done[to]) continue;
        assert(sub[to] <= sz / 2);
        insert(to, c, to, 0); 
        insert(to, c, to, 1);
    }
    for (int i : seen) f[i] = -1e9; seen.clear();
    reverse(g[c].begin(), g[c].end());
    for (int to : g[c]) {
        if (done[to]) continue;
        insert(to, c, to, 0);
        insert(to, c, to, 1);
    }
    for (int i : seen) f[i] = -1e9; seen.clear();
    done[c] = 1;
    for (int to : g[c]) {
        if (!done[to]) {
            decomp(to, c, sub[to]);
        }
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        f[i] = -1e9;
    }
    find_par(1, 0);
    decomp(1, 0, n);
    ans[n] = 1;
    for (int i = n; i >= 1; --i) {
        ans[i] = max(ans[i], ans[i + 1]);
    }
    for (int i = 1; i <= n; ++i) {
        if (i % 2 == 0) {
            cout << ans[i / 2] << '\n';
        } else {
            cout << "1\n";
        }
    }
}

Compilation message (stderr)

meetings2.cpp: In function 'void decomp(int, int, int)':
meetings2.cpp:85:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |     for (int i : seen) f[i] = -1e9; seen.clear();
      |     ^~~
meetings2.cpp:85:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |     for (int i : seen) f[i] = -1e9; seen.clear();
      |                                     ^~~~
meetings2.cpp:92:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   92 |     for (int i : seen) f[i] = -1e9; seen.clear();
      |     ^~~
meetings2.cpp:92:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   92 |     for (int i : seen) f[i] = -1e9; seen.clear();
      |                                     ^~~~

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