Submission #766557

#	Time	Username	Problem	Language	Result	Execution time	Memory
766557		caganyanmaz	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	298 ms	61888 KiB

Main

#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 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 23 / 23
• Subtask 7: 0 / 26