oj.uz

Submission #564208

# Submission time Handle Problem Language Result Execution time Memory
564208 2022-05-18T18:08:15 Z nikatamliani Meetings 2 (JOI21_meetings2) C++14
0 / 100
 6 ms 9704 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> g[N], subs[N];
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) {
    //     f[x] = max(f[x], y);
    //     x += x & -x;
    // }
    f[x] = max(f[x], y);
}
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 ans = -1e9;
    for (int i = x; i <= upper; ++i) {
        ans = max(ans, f[i]);
    }
    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 calc_dir() {
    calc(1, 0);
    find_par(1, 0);
}
void decomp(int x, int p, int sz) {
    calc(x, p);
    c = find_centroid(x, -1, sz);
    upper = sz;
    calc(c, p);
    for (int i = 1; i <= sz; ++i) {
        f[i] = -1e9;
    }
    for (int to : g[c]) {
        if (done[to]) continue;
        insert(to, c, to, 0); 
        insert(to, c, to, 1);
    }
    for (int i = 1; i <= sz; ++i) {
        f[i] = -1e9;
    }
    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 = 1; i <= sz; ++i) {
        f[i] = -1e9;
    }
    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);
    }
    calc_dir();
    decomp(1, 0, n);
    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";
        }
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Incorrect 5 ms 9704 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Incorrect 5 ms 9704 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Incorrect 5 ms 9704 KB Output isn't correct
6 Halted 0 ms 0 KB -