oj.uz

Submission #895016

# Submission time Handle Problem Language Result Execution time Memory
895016 2023-12-29T10:40:12 Z boris_mihov Constellation 3 (JOI20_constellation3) C++17
0 / 100
 3 ms 16732 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MOD = 1e9 + 7;

int n;
int in[MAXN];
int sz[MAXN];
int szC[MAXN];
int par[MAXN];
int dep[MAXN];
int out[MAXN];
int answer[MAXN];
std::vector <int> g[MAXN];
std::vector <int> c[MAXN];
int timer;

void buildDFS(int node, int p)
{
    par[node] = p;
    for (int &u : g[node])
    {
        if (u == par[node])
        {
            std::swap(u, g[node].back());
            break;
        }
    }
    
    in[node] = ++timer;
    sz[node] = 1;

    for (const int &u : g[node])
    {
        if (u == par[node])
        {
            continue;
        }

        buildDFS(u, node);
        sz[node] += sz[u];
    }

    out[node] = timer;
}

bool inSubtree(int x, int y)
{
    return in[y] <= in[x] && out[x] <= out[y];
}

int getSubtree(int node, int root)
{
    if (node == root)
    {
        return n;
    }

    if (!inSubtree(root, node))
    {
        return sz[node];
    }

    assert(g[node].size() >= 1 + (node != 1));
    int l = 0, r = g[node].size() - (node != 1), mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (in[root] < in[g[node][mid]]) r = mid;
        else l = mid;
    }
    
    // std::cout << "the fuck: " << node << ' ' << root << ' ' << g[node][l] << ' ' << inSubtree(root, g[node][l]) << '\n';
    assert(inSubtree(root, g[node][l]));
    return n - sz[g[node][l]];
}

int ans[MAXN];
int max[MAXN];
int maxIn[MAXN];
int from[MAXN];
int max2[MAXN];
bool vis[MAXN];
int output[MAXN];

void calcSZ(int node, int par)
{   
    szC[node] = 1;
    for (const int &u : g[node])
    {
        if (u == par || vis[u])
        {
            continue;
        }

        calcSZ(u, node);
        szC[node] += szC[u];
    }
}

int findCentroid(int node, int par, int size)
{
    for (const int &u : g[node])
    {
        if (u == par || vis[u])
        {
            continue;
        }

        if (szC[u] > size / 2)
        {
            return findCentroid(u, node, size);
        }
    }

    return node;
}

int decompose(int node, int d)
{
    calcSZ(node, 0);
    int cntr = findCentroid(node, 0, szC[node]);
    vis[cntr] = true;
    dep[cntr] = d;

    for (const int &u : g[cntr])
    {
        if (vis[u])
        {
            continue;
        }

        c[cntr].push_back(decompose(u, d + 1));
    }

    return cntr;
}

void addDFS(int node, int par, int dist, int lvl, int centroid)
{
    int currSize = getSubtree(node, centroid);
    ans[dist] = std::max(ans[dist], std::min(currSize, getSubtree(centroid, node)));
    maxIn[dist] = std::max(maxIn[dist], currSize);

    for (const int &u : g[node])
    {
        if (dep[u] > lvl && u != par)
        {
            addDFS(u, node, dist + 1, lvl, centroid);
        }
    }
}

void solveDFS(int node)
{
    for (const int &u : c[node])
    {
        solveDFS(u);
    }

    for (const int &u : g[node])
    {
        if (dep[u] < dep[node])
        {
            continue;
        }

        addDFS(u, node, 1, dep[node], node);
        for (int i = 1 ; i <= n && maxIn[i] > 0 ; ++i)
        {
            if (maxIn[i] > max[i])
            {
                max2[i] = max[i];
                max[i] = maxIn[i];
            } else if (maxIn[i] > max2[i])
            {
                max2[i] = maxIn[i];
            }

            maxIn[i] = 0;
        }
    }

    for (int l = 2 ; l <= n && (l / 2 == 0 || max[l / 2] > 0) ; ++l)
    {
        while (max[l] > max[l - 1]);
        while (max2[l] > max2[l - 1]);

        if (l % 2 == 0)
        {
            ans[l] = std::max(ans[l], max2[l / 2]);
            ans[l] = std::max(ans[l], max[l / 2 + 1]);
        } else
        {
            ans[l] = std::max(ans[l], max[l / 2 + 1]);
        }
    }

    for (int l = 1 ; l <= n && max[l] > 0 ; ++l)
    {
        max2[l] = max[l] = 0;
    }
}

void solve()
{
    buildDFS(1, 0);
    int root = decompose(1, 1);
    solveDFS(root);

    ans[0] = n;
    int ptr = 1;
    for (int dist = n ; dist >= 0 ; --dist)
    {
        while (2 * ptr <= n && ptr <= ans[dist])
        {
            output[2 * ptr] = dist + 1;
            ptr++;
        }
    }

    for (int i = 1 ; i <= n ; i += 2)
    {
        output[i] = 1;
    }
}

void print()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cout << output[i] << '\n';
    }
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i < n ; ++i)
    {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 16732 KB Output isn't correct
2 Halted 0 ms 0 KB -