답안 #782316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782316	2023-07-13T19:23:38 Z	borisAngelov	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	151 ms	46924 KB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const int max_log = 18;
const int inf = 1000000000;

int n;

vector<int> g[maxn];

int depth[maxn];
long long dp[maxn];

int permutation[maxn];

int jump[maxn][max_log];

void dfs(int node, int par, int dep)
{
    depth[node] = 1 + depth[par];

    for (auto next_node : g[node])
    {
        if (next_node != par)
        {
            jump[next_node][0] = node;
            dfs(next_node, node, dep + 1);
        }
    }
}

void build_sparse()
{
    for (int i = 0; i <= max_log - 1; ++i)
    {
        jump[1][i] = 1;
    }

    for (int i = 1; i <= max_log - 1; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            jump[j][i] = jump[jump[j][i - 1]][i - 1];
        }
    }
}

int find_lca(int x, int y)
{
    if (depth[x] < depth[y])
    {
        swap(x, y);
    }

    int diff = depth[x] - depth[y];

    for (int i = 0; i <= max_log - 1; ++i)
    {
        if ((diff & (1 << i)) != 0)
        {
            x = jump[x][i];

            diff -= (1 << i);

            if (diff == 0)
            {
                break;
            }
        }
    }

    if (x == y)
    {
        return x;
    }

    for (int i = max_log - 1; i >= 0; --i)
    {
        if (jump[x][i] != jump[y][i])
        {
            x = jump[x][i];
            y = jump[y][i];
        }
    }

    return jump[x][0];
}

int find_dist(int x, int y)
{
    return depth[x] + depth[y] - 2 * depth[find_lca(x, y)];
}

int parent[maxn];
int dsu_rank[maxn];
int component_current_root[maxn];

int find_root(int node)
{
    if (parent[node] == node)
    {
        return node;
    }

    return parent[node] = find_root(parent[node]);
}

void connect(int x, int y)
{
    x = find_root(x);
    y = find_root(y);

    if (x == y)
    {
        return;
    }

    if (dsu_rank[x] < dsu_rank[y])
    {
        swap(x, y);
    }

    if (dsu_rank[x] == dsu_rank[y])
    {
        ++dsu_rank[y];
    }

    parent[x] = y;
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> permutation[i];
    }

    for (int i = 1; i <= n - 1; ++i)
    {
        int x, y;
        cin >> x >> y;

        x = permutation[x];
        y = permutation[y];

        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1, -1, 0);

    build_sparse();

    /*for (int i = 1; i <= n; ++i)
    {
        for (int j = i + 1; j <= n; ++j)
        {
            cout << i << ' ' << j << ' ' << find_lca(i, j) << endl;
        }
    }*/

    for (int i = 1; i <= n; ++i)
    {
        dsu_rank[i] = 1;
        parent[i] = i;
        component_current_root[i] = i;
    }

    for (int node = 1; node <= n; ++node)
    {
        for (auto next_node : g[node])
        {
            if (next_node > node)
            {
                continue;
            }

            dp[node] = max(dp[node], dp[component_current_root[find_root(next_node)]] + find_dist(node, component_current_root[find_root(next_node)]));

            connect(node, next_node);
        }

        component_current_root[find_root(node)] = node;
    }

    cout << dp[n] << endl;

    return 0;
}

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	2 ms	5020 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	2 ms	5020 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	2 ms	5020 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	3 ms	5080 KB	Output is correct
14	Correct	3 ms	5024 KB	Output is correct
15	Correct	3 ms	5076 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	2 ms	5076 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	2 ms	5020 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	2 ms	5020 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	3 ms	5080 KB	Output is correct
14	Correct	3 ms	5024 KB	Output is correct
15	Correct	3 ms	5076 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	2 ms	5076 KB	Output is correct
18	Correct	4 ms	5844 KB	Output is correct
19	Correct	5 ms	5972 KB	Output is correct
20	Correct	4 ms	5972 KB	Output is correct
21	Correct	4 ms	5876 KB	Output is correct
22	Correct	4 ms	6056 KB	Output is correct
23	Correct	4 ms	5844 KB	Output is correct
24	Correct	5 ms	5972 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	2 ms	5020 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	2 ms	5020 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	3 ms	5080 KB	Output is correct
14	Correct	3 ms	5024 KB	Output is correct
15	Correct	3 ms	5076 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	2 ms	5076 KB	Output is correct
18	Correct	4 ms	5844 KB	Output is correct
19	Correct	5 ms	5972 KB	Output is correct
20	Correct	4 ms	5972 KB	Output is correct
21	Correct	4 ms	5876 KB	Output is correct
22	Correct	4 ms	6056 KB	Output is correct
23	Correct	4 ms	5844 KB	Output is correct
24	Correct	5 ms	5972 KB	Output is correct
25	Correct	2 ms	5028 KB	Output is correct
26	Correct	5 ms	5932 KB	Output is correct
27	Correct	4 ms	5932 KB	Output is correct
28	Correct	4 ms	5972 KB	Output is correct
29	Correct	4 ms	5928 KB	Output is correct
30	Correct	4 ms	5716 KB	Output is correct
31	Correct	4 ms	5716 KB	Output is correct
32	Correct	5 ms	5676 KB	Output is correct
33	Correct	4 ms	5716 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	2 ms	5020 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	2 ms	5020 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	3 ms	5080 KB	Output is correct
14	Correct	3 ms	5024 KB	Output is correct
15	Correct	3 ms	5076 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	2 ms	5076 KB	Output is correct
18	Correct	4 ms	5844 KB	Output is correct
19	Correct	5 ms	5972 KB	Output is correct
20	Correct	4 ms	5972 KB	Output is correct
21	Correct	4 ms	5876 KB	Output is correct
22	Correct	4 ms	6056 KB	Output is correct
23	Correct	4 ms	5844 KB	Output is correct
24	Correct	5 ms	5972 KB	Output is correct
25	Correct	96 ms	37828 KB	Output is correct
26	Correct	93 ms	46924 KB	Output is correct
27	Correct	95 ms	46904 KB	Output is correct
28	Correct	139 ms	46412 KB	Output is correct
29	Correct	142 ms	40940 KB	Output is correct
30	Correct	132 ms	44936 KB	Output is correct
31	Correct	148 ms	43700 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	2 ms	5076 KB	Output is correct
3	Correct	135 ms	31488 KB	Output is correct
4	Correct	125 ms	34428 KB	Output is correct
5	Correct	139 ms	34500 KB	Output is correct

Subtask #7
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	2 ms	5020 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	2 ms	4948 KB	Output is correct
10	Correct	2 ms	4948 KB	Output is correct
11	Correct	2 ms	5020 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	3 ms	5080 KB	Output is correct
14	Correct	3 ms	5024 KB	Output is correct
15	Correct	3 ms	5076 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	2 ms	5076 KB	Output is correct
18	Correct	4 ms	5844 KB	Output is correct
19	Correct	5 ms	5972 KB	Output is correct
20	Correct	4 ms	5972 KB	Output is correct
21	Correct	4 ms	5876 KB	Output is correct
22	Correct	4 ms	6056 KB	Output is correct
23	Correct	4 ms	5844 KB	Output is correct
24	Correct	5 ms	5972 KB	Output is correct
25	Correct	2 ms	5028 KB	Output is correct
26	Correct	5 ms	5932 KB	Output is correct
27	Correct	4 ms	5932 KB	Output is correct
28	Correct	4 ms	5972 KB	Output is correct
29	Correct	4 ms	5928 KB	Output is correct
30	Correct	4 ms	5716 KB	Output is correct
31	Correct	4 ms	5716 KB	Output is correct
32	Correct	5 ms	5676 KB	Output is correct
33	Correct	4 ms	5716 KB	Output is correct
34	Correct	96 ms	37828 KB	Output is correct
35	Correct	93 ms	46924 KB	Output is correct
36	Correct	95 ms	46904 KB	Output is correct
37	Correct	139 ms	46412 KB	Output is correct
38	Correct	142 ms	40940 KB	Output is correct
39	Correct	132 ms	44936 KB	Output is correct
40	Correct	148 ms	43700 KB	Output is correct
41	Correct	2 ms	4948 KB	Output is correct
42	Correct	2 ms	5076 KB	Output is correct
43	Correct	135 ms	31488 KB	Output is correct
44	Correct	125 ms	34428 KB	Output is correct
45	Correct	139 ms	34500 KB	Output is correct
46	Correct	105 ms	43340 KB	Output is correct
47	Correct	106 ms	43252 KB	Output is correct
48	Correct	107 ms	43364 KB	Output is correct
49	Correct	110 ms	43252 KB	Output is correct
50	Correct	150 ms	34656 KB	Output is correct
51	Correct	144 ms	34636 KB	Output is correct
52	Correct	151 ms	34668 KB	Output is correct
53	Correct	145 ms	34704 KB	Output is correct

답안 #782316

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 23.0 / 23.0

Subtask #7 26.0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
23.0 / 23.0

Subtask #7
26.0 / 26.0