oj.uz

Submission #766556

# Submission time Handle Problem Language Result Execution time Memory
766556 2023-06-25T21:30:25 Z caganyanmaz Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 281 ms 43532 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 = 2e5;
constexpr static int MXLOG = 20;
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 5 ms 9708 KB Output is correct
2 Correct 5 ms 9712 KB Output is correct
3 Correct 5 ms 9708 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9708 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9692 KB Output is correct
9 Correct 5 ms 9668 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 5 ms 9712 KB Output is correct
3 Correct 5 ms 9708 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9708 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9692 KB Output is correct
9 Correct 5 ms 9668 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9708 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9672 KB Output is correct
16 Correct 5 ms 9644 KB Output is correct
17 Correct 5 ms 9756 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 5 ms 9712 KB Output is correct
3 Correct 5 ms 9708 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9708 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9692 KB Output is correct
9 Correct 5 ms 9668 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9708 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9672 KB Output is correct
16 Correct 5 ms 9644 KB Output is correct
17 Correct 5 ms 9756 KB Output is correct
18 Correct 9 ms 10492 KB Output is correct
19 Correct 8 ms 10452 KB Output is correct
20 Correct 9 ms 10516 KB Output is correct
21 Correct 9 ms 10484 KB Output is correct
22 Correct 9 ms 10452 KB Output is correct
23 Correct 9 ms 10452 KB Output is correct
24 Correct 8 ms 10452 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 5 ms 9712 KB Output is correct
3 Correct 5 ms 9708 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9708 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9692 KB Output is correct
9 Correct 5 ms 9668 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9708 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9672 KB Output is correct
16 Correct 5 ms 9644 KB Output is correct
17 Correct 5 ms 9756 KB Output is correct
18 Correct 9 ms 10492 KB Output is correct
19 Correct 8 ms 10452 KB Output is correct
20 Correct 9 ms 10516 KB Output is correct
21 Correct 9 ms 10484 KB Output is correct
22 Correct 9 ms 10452 KB Output is correct
23 Correct 9 ms 10452 KB Output is correct
24 Correct 8 ms 10452 KB Output is correct
25 Correct 5 ms 9708 KB Output is correct
26 Correct 9 ms 10452 KB Output is correct
27 Correct 9 ms 10432 KB Output is correct
28 Correct 9 ms 10364 KB Output is correct
29 Correct 9 ms 10472 KB Output is correct
30 Correct 9 ms 10324 KB Output is correct
31 Correct 9 ms 10364 KB Output is correct
32 Correct 9 ms 10304 KB Output is correct
33 Correct 11 ms 10324 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 5 ms 9712 KB Output is correct
3 Correct 5 ms 9708 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9708 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9692 KB Output is correct
9 Correct 5 ms 9668 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9708 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9672 KB Output is correct
16 Correct 5 ms 9644 KB Output is correct
17 Correct 5 ms 9756 KB Output is correct
18 Correct 9 ms 10492 KB Output is correct
19 Correct 8 ms 10452 KB Output is correct
20 Correct 9 ms 10516 KB Output is correct
21 Correct 9 ms 10484 KB Output is correct
22 Correct 9 ms 10452 KB Output is correct
23 Correct 9 ms 10452 KB Output is correct
24 Correct 8 ms 10452 KB Output is correct
25 Incorrect 210 ms 43532 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 4 ms 9720 KB Output is correct
2 Correct 5 ms 9708 KB Output is correct
3 Correct 281 ms 38396 KB Output is correct
4 Correct 257 ms 38384 KB Output is correct
5 Correct 256 ms 38384 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9708 KB Output is correct
2 Correct 5 ms 9712 KB Output is correct
3 Correct 5 ms 9708 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9708 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9692 KB Output is correct
9 Correct 5 ms 9668 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9684 KB Output is correct
12 Correct 5 ms 9708 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9672 KB Output is correct
16 Correct 5 ms 9644 KB Output is correct
17 Correct 5 ms 9756 KB Output is correct
18 Correct 9 ms 10492 KB Output is correct
19 Correct 8 ms 10452 KB Output is correct
20 Correct 9 ms 10516 KB Output is correct
21 Correct 9 ms 10484 KB Output is correct
22 Correct 9 ms 10452 KB Output is correct
23 Correct 9 ms 10452 KB Output is correct
24 Correct 8 ms 10452 KB Output is correct
25 Correct 5 ms 9708 KB Output is correct
26 Correct 9 ms 10452 KB Output is correct
27 Correct 9 ms 10432 KB Output is correct
28 Correct 9 ms 10364 KB Output is correct
29 Correct 9 ms 10472 KB Output is correct
30 Correct 9 ms 10324 KB Output is correct
31 Correct 9 ms 10364 KB Output is correct
32 Correct 9 ms 10304 KB Output is correct
33 Correct 11 ms 10324 KB Output is correct
34 Incorrect 210 ms 43532 KB Output isn't correct
35 Halted 0 ms 0 KB -