Submission #895051

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
895051	2023-12-29T11:20:27 Z	boris_mihov	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	4000 ms	43248 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 update(int pos, int val)
    {
        update(1, n, 1, pos, val);
    }

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

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 resetDFS(int node, int par, int dist, int lvl, int centroid)
{
    int currSize = getSubtree(node, centroid);
    tree.update(currSize, 0);

    for (const int &u : g[node])
    {
        if (dep[u] > lvl && u != par)
        {
            resetDFS(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);
    }

    for (const int &u : g[node])
    {
        resetDFS(u, node, 1, dep[node], node);
    }

    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);
    }

    for (const int &u : g[node])
    {
        resetDFS(u, node, 1, dep[node], node);
    }
}

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:236:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |     for (int idx = 0 ; idx < g[node].size() ; ++idx)
      |                        ~~~~^~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	16984 KB	Output is correct
2	Correct	3 ms	16728 KB	Output is correct
3	Correct	3 ms	16732 KB	Output is correct
4	Correct	3 ms	16732 KB	Output is correct
5	Correct	3 ms	16800 KB	Output is correct
6	Correct	3 ms	16732 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	4 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	16828 KB	Output is correct
17	Correct	3 ms	16728 KB	Output is correct
18	Correct	3 ms	16732 KB	Output is correct
19	Correct	3 ms	16828 KB	Output is correct
20	Correct	3 ms	16732 KB	Output is correct
21	Correct	3 ms	16728 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	16984 KB	Output is correct
2	Correct	3 ms	16728 KB	Output is correct
3	Correct	3 ms	16732 KB	Output is correct
4	Correct	3 ms	16732 KB	Output is correct
5	Correct	3 ms	16800 KB	Output is correct
6	Correct	3 ms	16732 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	4 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	16828 KB	Output is correct
17	Correct	3 ms	16728 KB	Output is correct
18	Correct	3 ms	16732 KB	Output is correct
19	Correct	3 ms	16828 KB	Output is correct
20	Correct	3 ms	16732 KB	Output is correct
21	Correct	3 ms	16728 KB	Output is correct
22	Correct	13 ms	16988 KB	Output is correct
23	Correct	14 ms	16984 KB	Output is correct
24	Correct	16 ms	17408 KB	Output is correct
25	Correct	13 ms	16988 KB	Output is correct
26	Correct	17 ms	16988 KB	Output is correct
27	Correct	12 ms	17040 KB	Output is correct
28	Correct	13 ms	16988 KB	Output is correct
29	Correct	13 ms	16988 KB	Output is correct
30	Correct	12 ms	17124 KB	Output is correct
31	Correct	13 ms	17096 KB	Output is correct
32	Correct	20 ms	17232 KB	Output is correct
33	Correct	19 ms	17240 KB	Output is correct
34	Correct	49 ms	17108 KB	Output is correct
35	Correct	36 ms	16984 KB	Output is correct
36	Correct	13 ms	16984 KB	Output is correct
37	Correct	17 ms	16988 KB	Output is correct
38	Correct	21 ms	16988 KB	Output is correct

Subtask #3
0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	16984 KB	Output is correct
2	Correct	3 ms	16728 KB	Output is correct
3	Correct	3 ms	16732 KB	Output is correct
4	Correct	3 ms	16732 KB	Output is correct
5	Correct	3 ms	16800 KB	Output is correct
6	Correct	3 ms	16732 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	4 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	16828 KB	Output is correct
17	Correct	3 ms	16728 KB	Output is correct
18	Correct	3 ms	16732 KB	Output is correct
19	Correct	3 ms	16828 KB	Output is correct
20	Correct	3 ms	16732 KB	Output is correct
21	Correct	3 ms	16728 KB	Output is correct
22	Correct	13 ms	16988 KB	Output is correct
23	Correct	14 ms	16984 KB	Output is correct
24	Correct	16 ms	17408 KB	Output is correct
25	Correct	13 ms	16988 KB	Output is correct
26	Correct	17 ms	16988 KB	Output is correct
27	Correct	12 ms	17040 KB	Output is correct
28	Correct	13 ms	16988 KB	Output is correct
29	Correct	13 ms	16988 KB	Output is correct
30	Correct	12 ms	17124 KB	Output is correct
31	Correct	13 ms	17096 KB	Output is correct
32	Correct	20 ms	17232 KB	Output is correct
33	Correct	19 ms	17240 KB	Output is correct
34	Correct	49 ms	17108 KB	Output is correct
35	Correct	36 ms	16984 KB	Output is correct
36	Correct	13 ms	16984 KB	Output is correct
37	Correct	17 ms	16988 KB	Output is correct
38	Correct	21 ms	16988 KB	Output is correct
39	Correct	1416 ms	32112 KB	Output is correct
40	Correct	1301 ms	31848 KB	Output is correct
41	Correct	1423 ms	32148 KB	Output is correct
42	Correct	1431 ms	32368 KB	Output is correct
43	Correct	1429 ms	32596 KB	Output is correct
44	Correct	1335 ms	32420 KB	Output is correct
45	Correct	2443 ms	37308 KB	Output is correct
46	Correct	2195 ms	43248 KB	Output is correct
47	Execution timed out	4034 ms	31452 KB	Time limit exceeded
48	Halted	0 ms	0 KB	-

Submission #895051

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 16.0 / 16.0

Subtask #3 0 / 80.0

Subtask #1
4.0 / 4.0

Subtask #2
16.0 / 16.0

Subtask #3
0 / 80.0