Submission #895056

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
895056	2023-12-29T11:22:56 Z	boris_mihov	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	2321 ms	39236 KB

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

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.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	16728 KB	Output is correct
2	Correct	4 ms	16732 KB	Output is correct
3	Correct	4 ms	16820 KB	Output is correct
4	Correct	3 ms	16732 KB	Output is correct
5	Correct	3 ms	16732 KB	Output is correct
6	Correct	3 ms	16732 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	3 ms	16732 KB	Output is correct
9	Correct	3 ms	16732 KB	Output is correct
10	Correct	3 ms	16732 KB	Output is correct
11	Correct	3 ms	16732 KB	Output is correct
12	Correct	3 ms	16732 KB	Output is correct
13	Correct	3 ms	16732 KB	Output is correct
14	Correct	3 ms	16732 KB	Output is correct
15	Correct	3 ms	16732 KB	Output is correct
16	Correct	3 ms	16732 KB	Output is correct
17	Correct	3 ms	16796 KB	Output is correct
18	Correct	3 ms	16728 KB	Output is correct
19	Correct	3 ms	16732 KB	Output is correct
20	Correct	3 ms	16732 KB	Output is correct
21	Correct	3 ms	16732 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	16728 KB	Output is correct
2	Correct	4 ms	16732 KB	Output is correct
3	Correct	4 ms	16820 KB	Output is correct
4	Correct	3 ms	16732 KB	Output is correct
5	Correct	3 ms	16732 KB	Output is correct
6	Correct	3 ms	16732 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	3 ms	16732 KB	Output is correct
9	Correct	3 ms	16732 KB	Output is correct
10	Correct	3 ms	16732 KB	Output is correct
11	Correct	3 ms	16732 KB	Output is correct
12	Correct	3 ms	16732 KB	Output is correct
13	Correct	3 ms	16732 KB	Output is correct
14	Correct	3 ms	16732 KB	Output is correct
15	Correct	3 ms	16732 KB	Output is correct
16	Correct	3 ms	16732 KB	Output is correct
17	Correct	3 ms	16796 KB	Output is correct
18	Correct	3 ms	16728 KB	Output is correct
19	Correct	3 ms	16732 KB	Output is correct
20	Correct	3 ms	16732 KB	Output is correct
21	Correct	3 ms	16732 KB	Output is correct
22	Correct	9 ms	16988 KB	Output is correct
23	Correct	9 ms	16988 KB	Output is correct
24	Correct	9 ms	17084 KB	Output is correct
25	Correct	10 ms	17080 KB	Output is correct
26	Correct	9 ms	16988 KB	Output is correct
27	Correct	9 ms	16988 KB	Output is correct
28	Correct	11 ms	17088 KB	Output is correct
29	Correct	9 ms	16988 KB	Output is correct
30	Correct	9 ms	16988 KB	Output is correct
31	Correct	9 ms	16988 KB	Output is correct
32	Correct	14 ms	17172 KB	Output is correct
33	Correct	15 ms	17244 KB	Output is correct
34	Correct	6 ms	17116 KB	Output is correct
35	Correct	4 ms	17240 KB	Output is correct
36	Correct	9 ms	16984 KB	Output is correct
37	Correct	5 ms	16984 KB	Output is correct
38	Correct	11 ms	16988 KB	Output is correct

Subtask #3
80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	16728 KB	Output is correct
2	Correct	4 ms	16732 KB	Output is correct
3	Correct	4 ms	16820 KB	Output is correct
4	Correct	3 ms	16732 KB	Output is correct
5	Correct	3 ms	16732 KB	Output is correct
6	Correct	3 ms	16732 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	3 ms	16732 KB	Output is correct
9	Correct	3 ms	16732 KB	Output is correct
10	Correct	3 ms	16732 KB	Output is correct
11	Correct	3 ms	16732 KB	Output is correct
12	Correct	3 ms	16732 KB	Output is correct
13	Correct	3 ms	16732 KB	Output is correct
14	Correct	3 ms	16732 KB	Output is correct
15	Correct	3 ms	16732 KB	Output is correct
16	Correct	3 ms	16732 KB	Output is correct
17	Correct	3 ms	16796 KB	Output is correct
18	Correct	3 ms	16728 KB	Output is correct
19	Correct	3 ms	16732 KB	Output is correct
20	Correct	3 ms	16732 KB	Output is correct
21	Correct	3 ms	16732 KB	Output is correct
22	Correct	9 ms	16988 KB	Output is correct
23	Correct	9 ms	16988 KB	Output is correct
24	Correct	9 ms	17084 KB	Output is correct
25	Correct	10 ms	17080 KB	Output is correct
26	Correct	9 ms	16988 KB	Output is correct
27	Correct	9 ms	16988 KB	Output is correct
28	Correct	11 ms	17088 KB	Output is correct
29	Correct	9 ms	16988 KB	Output is correct
30	Correct	9 ms	16988 KB	Output is correct
31	Correct	9 ms	16988 KB	Output is correct
32	Correct	14 ms	17172 KB	Output is correct
33	Correct	15 ms	17244 KB	Output is correct
34	Correct	6 ms	17116 KB	Output is correct
35	Correct	4 ms	17240 KB	Output is correct
36	Correct	9 ms	16984 KB	Output is correct
37	Correct	5 ms	16984 KB	Output is correct
38	Correct	11 ms	16988 KB	Output is correct
39	Correct	755 ms	27576 KB	Output is correct
40	Correct	739 ms	27432 KB	Output is correct
41	Correct	894 ms	27612 KB	Output is correct
42	Correct	776 ms	27864 KB	Output is correct
43	Correct	863 ms	27728 KB	Output is correct
44	Correct	879 ms	27844 KB	Output is correct
45	Correct	1624 ms	33636 KB	Output is correct
46	Correct	2321 ms	39236 KB	Output is correct
47	Correct	256 ms	27240 KB	Output is correct
48	Correct	182 ms	28948 KB	Output is correct
49	Correct	1027 ms	31068 KB	Output is correct
50	Correct	236 ms	28996 KB	Output is correct
51	Correct	1006 ms	36676 KB	Output is correct

Submission #895056

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 16.0 / 16.0

Subtask #3 80.0 / 80.0

Subtask #1
4.0 / 4.0

Subtask #2
16.0 / 16.0

Subtask #3
80.0 / 80.0