oj.uz

Submission #605008

# Submission time Handle Problem Language Result Execution time Memory
605008 2022-07-25T12:11:31 Z elkernos Meetings 2 (JOI21_meetings2) C++17
0 / 100
 3 ms 520 KB 
#include <bits/stdc++.h>

using namespace std;

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    vector<int> sub(n + 1);
    function<void(int, int)> subsz = [&](int u, int p) {
        sub[u] = 1;
        for(int to : g[u]) {
            if(to == p) {
                continue;
            }
            subsz(to, u);
            sub[u] += sub[to];
        }
    };
    subsz(1, 1);
    function<int(int, int, int)> getcen = [&](int u, int p, int d) {
        for(int to : g[u]) {
            if(to == p) {
                continue;
            }
            if(sub[to] > d / 2) {
                return getcen(to, u, sub[to]);
            }
        }
        return u;
    };
    int root = getcen(1, 1, n);
    vector<vector<int>> up(20, vector<int>(n + 1));
    vector<int> dep(n + 1);
    function<void(int, int)> prep = [&](int u, int p) {
        for(int to : g[u]) {
            if(to == p) {
                continue;
            }
            dep[to] = dep[u] + 1;
            up[0][to] = u;
            sub[to] = 1;
            prep(to, u);
            sub[u] += sub[to];
        }
    };
    up[0][root] = root;
    sub[root] = 1;
    prep(root, root);
    vector<vector<int>> gg(n / 2 + 1);
    for(int i = 1; i <= n; i++) {
        if(i == root) {
            continue;
        }
        gg[sub[i]].emplace_back(i);
    }
    for(int i = 1; i < 20; i++) {
        for(int j = 1; j <= n; j++) {
            up[i][j] = up[i - 1][up[i - 1][j]];
        }
    }
    auto jump = [&](int u, int d) {
        for(int i = 0; d; i++) {
            if(d % 2) {
                u = up[i][u];
            }
            d /= 2;
        }
        return u;
    };
    auto lca = [&](int a, int b) {
        if(dep[a] > dep[b]) {
            swap(a, b);
        }
        b = jump(b, dep[b] - dep[a]);
        if(a == b) {
            return a;
        }
        for(int i = 19; i >= 0; i--) {
            if(up[i][a] != up[i][b]) {
                a = up[i][a];
                b = up[i][b];
            }
        }
        return up[0][a];
    };
    auto d = [&](int a, int b) {
        return dep[a] + dep[b] - dep[lca(a, b)];
    };
    int a = root, b = root, c = 0;
    vector<int> ans(n / 2 + 1);
    for(int i = n / 2; i >= 1; i--) {
        for(int j : gg[i]) {
            int one = d(a, j);
            int two = d(b, j);
            if(one > c) {
                b = j;
                c = one;
            }
            else if(two > c) {
                a = j;
                c = two;
            }
        }
        ans[i] = c;
    }
    for(int i = 1; i <= n; i++) {
        cout << (i % 2 ? 1 : ans[i / 2] + 1) << '\n';
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Runtime error 3 ms 520 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Runtime error 3 ms 520 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Runtime error 3 ms 520 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -