Submission #895056

#	Time	Username	Problem	Language	Result	Execution time	Memory
895056		boris_mihov	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	2321 ms	39236 KiB

meetings2

#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;
struct SegmentTree
{
    int tree[4 * MAXN];
    void update(int l, int r, int node, int queryPos, int queryVal)
    {
        if (l == r)
        {
            if (queryVal == 0) tree[node] = queryVal;
            else tree[node] = std::max(tree[node], queryVal);
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
        else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
        tree[node] = std::max(tree[2*node], tree[2*node + 1]);
    }

    int findMAX(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        int res = 0;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = std::max(res, findMAX(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) res = std::max(res, findMAX(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void reset(int l, int r, int node)
    {
        tree[node] = 0;
        if (l != r)
        {
            int mid = (l + r) / 2;
            if (tree[2*node] != 0)
            {
                reset(l, mid, 2*node);
            }

            if (tree[2*node + 1] != 0)
            {
                reset(mid + 1, r, 2*node + 1);
            }
        }
    }

    void update(int pos, int val)
    {
        update(1, n, 1, pos, val);
    }

    int findMAX(int l, int r)
    {
        return findMAX(1, n, 1, l, r);
    }

    void reset()
    {
        reset(1, n, 1);
    }
};

int in[MAXN];
int sz[MAXN];
int szC[MAXN];
int par[MAXN];
int dep[MAXN];
int out[MAXN];
int answer[MAXN];
SegmentTree tree;
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;
    }
    
    assert(inSubtree(root, g[node][l]));
    return n - sz[g[node][l]];
}

int ans[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 checkDFS(int node, int par, int dist, int lvl, int centroid)
{
    int currSize = getSubtree(node, centroid);
    int centroidSize = std::min(currSize, getSubtree(centroid, node));
    ans[centroidSize] = std::max(ans[centroidSize], dist);

    int res = tree.findMAX(currSize, n);
    if (res != 0) ans[currSize] = std::max(ans[currSize], dist + res);

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

void addDFS(int node, int par, int dist, int lvl, int centroid)
{
    int currSize = getSubtree(node, centroid);
    tree.update(currSize, dist);

    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 (int idx = 0 ; idx < g[node].size() ; ++idx)
    {
        int u = g[node][idx];
        if (dep[u] < dep[node])
        {
            continue;
        }
        
        checkDFS(u, node, 1, dep[node], node);
        addDFS(u, node, 1, dep[node], node);
    }

    tree.reset();
    for (int idx = (int)g[node].size() - 1 ; idx >= 0 ; --idx)
    {
        int u = g[node][idx];
        if (dep[u] < dep[node])
        {
            continue;
        }
        
        checkDFS(u, node, 1, dep[node], node);
        addDFS(u, node, 1, dep[node], node);
    }

    tree.reset();
}

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

    for (int i = n - 1 ; i >= 1 ; --i)
    {
        ans[i] = std::max(ans[i], ans[i + 1]);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (i & 1) output[i] = 1;
        else output[i] = ans[i / 2] + 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;
}

/*
14 13
10 14
3 10
14 13
1 3
3 5
3 11
12 14
14 6
11 8
2 3
7 8
9 7
1 4

*/

Compilation message (stderr)

meetings2.cpp: In function 'void solveDFS(int)':
meetings2.cpp:245:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |     for (int idx = 0 ; idx < g[node].size() ; ++idx)
      |                        ~~~~^~~~~~~~~~~~~~~~

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