Submission #769300

#	Time	Username	Problem	Language	Result	Execution time	Memory
769300		danikoynov	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	513 ms	77932 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;

int n, a[maxn], used[maxn], pos[maxn];
vector < int > adj[maxn];
ll dp[maxn];
int rec(int val)
{
    if (used[val])
        return dp[val];
    used[val] = 1;
    int left = 0, right = n + 1;
    for (int i = n; i > val; i --)
    {
        if (pos[i] > pos[val])
        {
            right = min(right, pos[i]);
        }
        else
        {
            left = max(left, pos[i]);
        }
    }

    int mx = -1;
    for (int i = pos[val] + 1; i < right; i ++)
    {
        if (a[i] > mx)
        {
            mx = a[i];
            dp[val] = max(dp[val], (ll)(i - pos[val] + rec(a[i])));
        }
    }
    mx = -1;
    for (int i = pos[val] - 1; i > left; i --)
    {
        if (a[i] > mx)
        {
            mx = a[i];
            dp[val] = max(dp[val], (ll)(pos[val] - i + rec(a[i])));
        }
    }
    return dp[val];
}

int dfs(int v, int p, int mx, int dis, int val)
{
    if (mx > val)
        return 0;

    int ans = 0;
    if (a[v] == mx)
        ans = max((ll)ans, dis + dp[v]);

    for (int u : adj[v])
    {
        if (u == p)
            continue;
        ans = max(ans, dfs(u, v, max(mx, a[u]), dis + 1, val));

    }

    return ans;
}

int best[maxn], par[maxn], depth[maxn];
int tin[maxn], tout[maxn], timer, heavy[maxn];
int occ[2 * maxn], sub[maxn];

void trav(int v)
{
    occ[++ timer] = v;
    tin[v] = timer;
    heavy[v] = -1;
    sub[v] = 1;
    for (int u : adj[v])
    {
        if (u == par[v])
            continue;
        depth[u] = depth[v] + 1;
        par[u] = v;
        trav(u);
        sub[v] += sub[u];
        if (heavy[v] == -1 || sub[heavy[u]] > sub[heavy[v]])
            heavy[v] = u;
        occ[++ timer] = v;
    }
    tout[v] = timer;
}

const int maxlog = 20;
int fp[maxlog][2 * maxn], lg[2 * maxn];

void build_sparse_table()
{
    for (int i = 1; i <= timer; i ++)
    {
        lg[i] = lg[i / 2] + 1;
        fp[0][i] = occ[i];
    }

    for (int j = 1; j < lg[timer]; j ++)
        for (int i = 1; i <= timer - (1 << j) + 1; i ++)
        {
            fp[j][i] = fp[j - 1][i + (1 << (j - 1))];
            if (depth[fp[j - 1][i]] < depth[fp[j][i]])
                fp[j][i] = fp[j - 1][i];
        }
}

int lca_query(int v, int u)
{
    int l = tin[v], r = tin[u];
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1] - 1, lca = fp[len][r - (1 << len) + 1];
    if (depth[fp[len][l]] < depth[lca])
        lca = fp[len][l];
    return lca;
}

int distance(int v, int u)
{
    return depth[v] + depth[u] - 2 * depth[lca_query(v, u)];
}

struct chain
{
    int left, right, head;

    chain()
    {
        left = 0;
        right = 0;
        head = 0;
    }
} chains[maxn];

int chain_count, chain_idx[maxn], chain_pos[maxn];
int order[maxn];
void hld(int v)
{
    chain_idx[v] = chain_count;
    chain_pos[v] = ++ chains[chain_count].right;
    order[chains[chain_count].right] = v;
    if (heavy[v] != -1)
    {
        hld(heavy[v]);
    }
    for (int u : adj[v])
    {
        if (u == par[v] || u == heavy[v])
            continue;
        chain_count ++;
        chains[chain_count].left = chains[chain_count - 1].right + 1;
        chains[chain_count].right = chains[chain_count - 1].right;
        chains[chain_count].head = u;
        hld(u);
    }
}

int tree[4 * maxn], lazy[4 * maxn];

void propagate(int root, int left, int right)
{
    if (lazy[root] == 0)
        return;

    if (left != right)
    {
        tree[root * 2] = lazy[root];
        tree[root * 2 + 1] = lazy[root];
        lazy[root * 2] = lazy[root];
        lazy[root * 2 + 1] = lazy[root];
    }
    lazy[root] = 0;
}

void update(int root, int left, int right, int qleft, int qright, int val)
{
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        tree[root] = val;
        lazy[root] = val;
        return;
    }


    propagate(root, left, right);
    int mid = (left + right) / 2;
    update(root * 2, left, mid, qleft, qright, val);
    update(root * 2 + 1, mid + 1, right, qleft, qright, val);
    tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}

int query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return 0;
    if (left >= qleft && right <= qright)
        return tree[root];
    propagate(root, left, right);
    int mid = (left + right) / 2;
    return max(query(root * 2, left, mid, qleft, qright),
               query(root * 2 + 1, mid + 1, right, qleft, qright));
}

int lead[maxn], lf_lead[maxn], rf_lead[maxn];

int find_leader(int v)
{
    if (v == lead[v])
        return v;
    return (lead[v] = find_leader(lead[v]));
}

void unite(int v, int u)
{
    ///cout << "unite " << v << " " << u << endl;
    v = find_leader(v);
    u = find_leader(u);
    if (v == u)
        return;
    lf_lead[v] = min(lf_lead[v], lf_lead[u]);
    rf_lead[v] = max(rf_lead[v], rf_lead[u]);
    lead[u] = v;
}

int active[maxn];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        pos[a[i]] = i;
    }


    bool chain = true;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        if (!(v == i && u == i + 1))
            chain = false;

        adj[v].push_back(u);
        adj[u].push_back(v);
    }




    trav(1);
    build_sparse_table();
    timer = 0;
    chain_count = 1;
    chains[chain_count].left = 1;
    chains[chain_count].right = 0;
    chains[chain_count].head = 1;
    hld(1);
    /**for (int i = 1; i <= chain_count; i ++)
    {
        cout << "chain " << i << endl;
        for (int j = chains[i].left; j <= chains[i].right; j ++)
            cout << order[j] << " ";
        cout << endl;
    }*/

    for (int i = 1; i <= n; i ++)
    {
        lf_lead[i] = rf_lead[i] = lead[i] = i;
    }

    for (int i = 1; i <= n; i ++)
    {

        int v = pos[i];
        active[v] = 1;
        //cout << "step" << endl;
        //cout << v << endl;
        for (int u : adj[v])
        {
            ///cout << u << endl;
            if (u == par[v])
                continue;
            ///cout << "fine" << endl;
            int cur = query(1, 1, n, chain_pos[u], chain_pos[u]);
            ///cout << chain_pos[u] << " : " << chain_pos[u] << endl;
            if (cur != 0)
            {
                ///cout << "check " << cur << endl;
                dp[v] = max(dp[v], dp[pos[cur]] + distance(v, pos[cur]));
            }
        }

        if (active[order[chain_pos[v] - 1]])
            unite(chain_pos[v] - 1, chain_pos[v]); ///cout << "yep" << endl;
        if (active[order[chain_pos[v] + 1]])
            unite(chain_pos[v] + 1, chain_pos[v]);

        //cout << "Bef " << order[chain_pos[v] - 1] << " " << active[order[chain_pos[v] - 1]] << endl;
        int cur_idx = chain_idx[v], cur_pos = chain_pos[v];
        while(true)
        {
            if (a[order[cur_pos]] > i)
                break;
            int cur_lead = find_leader(cur_pos), lf = chains[cur_idx].left, rf = cur_pos;
            lf = max(lf, lf_lead[cur_lead]);
            int cur_best = query(1, 1, n, lf, rf);
            ///cout << "check " << cur_best << " range " << lf << " " << rf << " " << lf_lead[cur_lead] << endl;
            ///cout << active[order[lf_lead[cur_lead]]] << endl;
            if (cur_best != 0)
                dp[v] = max(dp[v], dp[pos[cur_best]] + distance(v, pos[cur_best]));

            if (lf_lead[cur_lead] > chains[cur_idx].left || par[chains[cur_idx].head] == 0)
                break;

            cur_pos = chain_pos[par[chains[cur_idx].head]];
            cur_idx = chain_idx[order[cur_pos]];
        }

        cur_idx = chain_idx[v];
        cur_pos = chain_pos[v];

        while(true)
        {
            if (a[order[cur_pos]] > i)
                break;
            int cur_lead = find_leader(cur_pos), lf = chains[cur_idx].left, rf = cur_pos;
            lf = max(lf, lf_lead[cur_lead]);
            update(1, 1, n, lf, rf, i);
            ///cout << "updated " << lf << " " << rf << endl;
            if (lf_lead[cur_lead] > chains[cur_idx].left || par[chains[cur_idx].head] == 0)
                break;

            cur_pos = chain_pos[par[chains[cur_idx].head]];
            cur_idx = chain_idx[order[cur_pos]];
        }
        ///cout << "dp " << v << " " << dp[v] << endl;
    }

    cout << dp[pos[n]] << endl;



}

int main()
{
    speed();
    solve();
    return 0;
}
/**
8
5 3 8 7 4 6 1 2
1 2
2 4
2 5
3 6
1 3
3 7
2 8

*/

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:255:10: warning: variable 'chain' set but not used [-Wunused-but-set-variable]
  255 |     bool chain = true;
      |          ^~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26