oj.uz

Submission #766557

# Submission time Handle Problem Language Result Execution time Memory
766557 2023-06-25T21:33:22 Z caganyanmaz Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 298 ms 61888 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
//#define DEBUGGING
#ifdef DEBUGGING
#define debug(x) cout << (#x) << ": " << (x) << endl;
#else
#define debug(x)
#endif


struct Node
{
        int head, tail, size, nxt, move_sum, max_node;
        Node(int index) : head(index), tail(index), size(1), nxt(-1), move_sum(0), max_node(-1) {}
        Node() : Node(-1) {}
};

constexpr static int MXSIZE = 5e5;
constexpr static int MXLOG = 30;
int v[MXSIZE];
array<int,2> sv[MXSIZE];
vector<int> g[MXSIZE];
int bl[MXSIZE][MXLOG];
int depth[MXSIZE];
Node node[MXSIZE];

void dfs(int node, int parent, int d);
void process_bl(int n);
int advance(int node, int steps);
int find_lca(int a, int b);
int get_dist(int a, int b);
void merge(int a, int b);

int main()
{
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) cin >> v[i];
        for (int i = 0; i < n-1; i++)
        {
                int a, b;
                cin >> a >> b;
                a--,b--;
                g[a].pb(b);
                g[b].pb(a);
        }
        dfs(0, 0, 0);
        process_bl(n);
        for (int i = 0; i < n; i++)
                node[i] = Node(i);
        for (int i = 0; i < n; i++)
                sv[i][0] = v[i], sv[i][1] = i;
        sort(sv, sv + n);
        for (int j = 0; j < n; j++)
        {
                int i = sv[j][1];
                int best_sum = 0;
                for (int c : g[i])
                {
                        if (v[i] > v[c])
                        {
                                best_sum = max(best_sum, node[node[c].head].move_sum + get_dist(node[node[c].head].max_node, i));
                                merge(node[i].head, node[c].head);
                        }
                }
                debug(i);
                debug(node[i].head);
                debug(best_sum);
                node[node[i].head].move_sum = best_sum;
                node[node[i].head].max_node = i;
        }
        cout << node[node[0].head].move_sum << "\n";
}

void dfs(int node, int parent, int d)
{
        bl[node][0] = parent;
        depth[node] = d;
        for (int c : g[node])
                if (c != parent)
                        dfs(c, node, d+1);
}

void process_bl(int n)
{
        for (int i = 1; i < MXLOG; i++)
                for (int j = 0; j < n; j++)
                        bl[j][i] = bl[bl[j][i-1]][i-1];
}

int advance(int node, int steps)
{
        for (int i = 0; i < MXLOG; i++)
                if (steps&(1<<i))
                        node = bl[node][i];
        return node;
}

int find_lca(int a, int b)
{
        if (depth[a] > depth[b]) swap(a, b);
        b = advance(b, depth[b]-depth[a]);
        if (a == b) return a;
        for (int i = MXLOG-1; i >= 0; i--)
                if (bl[a][i] != bl[b][i])
                        a = bl[a][i], b = bl[b][i];
        return bl[a][0];
}

int get_dist(int a, int b)
{
        return depth[a] + depth[b] - depth[find_lca(a, b)] * 2;
}

void merge(int a, int b)
{
        if (node[b].size > node[a].size) swap(a, b);
        node[a].size += node[b].size;
        node[node[a].tail].nxt = node[b].head;
        node[a].tail = node[b].tail;
        while (b != -1)
        {
                node[b].head = a;
                b = node[b].nxt;
        }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23732 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 11 ms 23696 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23732 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 11 ms 23696 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 11 ms 23868 KB Output is correct
12 Correct 11 ms 23744 KB Output is correct
13 Correct 11 ms 23800 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23796 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23732 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 11 ms 23696 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 11 ms 23868 KB Output is correct
12 Correct 11 ms 23744 KB Output is correct
13 Correct 11 ms 23800 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23796 KB Output is correct
18 Correct 17 ms 24660 KB Output is correct
19 Correct 16 ms 24644 KB Output is correct
20 Correct 15 ms 24728 KB Output is correct
21 Correct 16 ms 24700 KB Output is correct
22 Correct 16 ms 24704 KB Output is correct
23 Correct 16 ms 24720 KB Output is correct
24 Correct 17 ms 24736 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23732 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 11 ms 23696 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 11 ms 23868 KB Output is correct
12 Correct 11 ms 23744 KB Output is correct
13 Correct 11 ms 23800 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23796 KB Output is correct
18 Correct 17 ms 24660 KB Output is correct
19 Correct 16 ms 24644 KB Output is correct
20 Correct 15 ms 24728 KB Output is correct
21 Correct 16 ms 24700 KB Output is correct
22 Correct 16 ms 24704 KB Output is correct
23 Correct 16 ms 24720 KB Output is correct
24 Correct 17 ms 24736 KB Output is correct
25 Correct 11 ms 23816 KB Output is correct
26 Correct 16 ms 24592 KB Output is correct
27 Correct 16 ms 24640 KB Output is correct
28 Correct 16 ms 24568 KB Output is correct
29 Correct 17 ms 24788 KB Output is correct
30 Correct 16 ms 24532 KB Output is correct
31 Correct 16 ms 24528 KB Output is correct
32 Correct 16 ms 24560 KB Output is correct
33 Correct 16 ms 24532 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23732 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 11 ms 23696 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 11 ms 23868 KB Output is correct
12 Correct 11 ms 23744 KB Output is correct
13 Correct 11 ms 23800 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23796 KB Output is correct
18 Correct 17 ms 24660 KB Output is correct
19 Correct 16 ms 24644 KB Output is correct
20 Correct 15 ms 24728 KB Output is correct
21 Correct 16 ms 24700 KB Output is correct
22 Correct 16 ms 24704 KB Output is correct
23 Correct 16 ms 24720 KB Output is correct
24 Correct 17 ms 24736 KB Output is correct
25 Incorrect 237 ms 61888 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23848 KB Output is correct
3 Correct 298 ms 56664 KB Output is correct
4 Correct 287 ms 56664 KB Output is correct
5 Correct 291 ms 56612 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23732 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 11 ms 23696 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 11 ms 23868 KB Output is correct
12 Correct 11 ms 23744 KB Output is correct
13 Correct 11 ms 23800 KB Output is correct
14 Correct 12 ms 23892 KB Output is correct
15 Correct 12 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23796 KB Output is correct
18 Correct 17 ms 24660 KB Output is correct
19 Correct 16 ms 24644 KB Output is correct
20 Correct 15 ms 24728 KB Output is correct
21 Correct 16 ms 24700 KB Output is correct
22 Correct 16 ms 24704 KB Output is correct
23 Correct 16 ms 24720 KB Output is correct
24 Correct 17 ms 24736 KB Output is correct
25 Correct 11 ms 23816 KB Output is correct
26 Correct 16 ms 24592 KB Output is correct
27 Correct 16 ms 24640 KB Output is correct
28 Correct 16 ms 24568 KB Output is correct
29 Correct 17 ms 24788 KB Output is correct
30 Correct 16 ms 24532 KB Output is correct
31 Correct 16 ms 24528 KB Output is correct
32 Correct 16 ms 24560 KB Output is correct
33 Correct 16 ms 24532 KB Output is correct
34 Incorrect 237 ms 61888 KB Output isn't correct
35 Halted 0 ms 0 KB -