Submission #939390

#	Time	Username	Problem	Language	Result	Execution time	Memory
939390		serkanrashid	Cat Exercise (JOI23_ho_t4)	C++14	31 / 100	2065 ms	442420 KiB

Main

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

using namespace std;

struct Node
{
    int ch,num;
    Node(){};
    Node(int chi, int ni)
    {
        ch = chi;
        num = ni;
    }
};

const int maxn = 2*1e5+5;

int n,p[maxn],pos[maxn];
int in[maxn],ou[maxn];

int jump[maxn][20],lvl[maxn];

int lazy[4*maxn];
Node tree[4*maxn];
vector<int>g[maxn];
int timer,ql,qr;

void make_tree(int v, int l, int r)
{
    if(l==r)
    {
        tree[v].ch = p[pos[r]];
        tree[v].num = pos[r];
        return;
    }
    int mid = (l+r)/2;
    make_tree(v*2+0,l,mid+0);
    make_tree(v*2+1,mid+1,r);
    if(tree[v*2+0].ch>tree[v*2+1].ch) tree[v] = tree[v*2+0];
    else tree[v] = tree[v*2+1];
}

void push_lazy(int v, int l, int r)
{
    if(!lazy[v]) return;
    tree[v] = {0,0};
    lazy[v*2+0] = 1;
    lazy[v*2+1] = 1;
    lazy[v] = 0;
}

Node query(int v, int l, int r)
{
    push_lazy(v,l,r);
    if(r<ql||qr<l||l>r) return {0,0};
    if(ql<=l&&r<=qr) return tree[v];
    int mid = (l+r)/2;
    Node q1 = query(v*2+0,l,mid+0);
    Node q2 = query(v*2+1,mid+1,r);
    if(q1.ch>q2.ch) return q1;
    else return q2;
}

void update(int v, int l, int r)
{
    push_lazy(v,l,r);
    if(r<ql||qr<l||l>r) return;
    if(ql<=l&&r<=qr)
    {
        lazy[v] = 1;
        push_lazy(v,l,r);
        return;
    }
    int mid = (l+r)/2;
    update(v*2+0,l,mid+0);
    update(v*2+1,mid+1,r);
    if(tree[v*2+0].ch>tree[v*2+1].ch) tree[v] = tree[v*2+0];
    else tree[v] = tree[v*2+1];
}

void read()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> p[i];
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
}

bool cmp(int p1, int p2)
{
    return in[p1]<in[p2];
}

void dfs(int beg, int par)
{
    in[beg] = ++timer;
    jump[beg][0] = par;
    lvl[beg] = lvl[par]+1;
    for(int nb:g[beg]) if(nb!=par) dfs(nb,beg);
    ou[beg] = timer;
}

int lca(int a, int b)
{
    int raz = abs(lvl[a]-lvl[b]);
    for(int j=0;j<20;j++)
    {
        if(raz&(1<<j))
        {
            if(lvl[a]>lvl[b]) a = jump[a][j];
            else b = jump[b][j];
        }
    }
    if(a==b) return a;
    for(int j=19;j>=0;j--)
    {
        if(jump[a][j]!=jump[b][j])
        {
            a = jump[a][j];
            b = jump[b][j];
        }
    }
    return jump[a][0];
}

long long dist(int a, int b)
{
    if(a==0||b==0) return 0;
    return lvl[a]+lvl[b]-2*lvl[lca(a,b)];
}

void pre()
{
    dfs(1,1);
    for(int i=1;i<=n;i++) pos[i] = i;
    sort(pos+1,pos+n+1,cmp);
    make_tree(1,1,n);
    for(int j=1;j<20;j++)
    {
        for(int i=1;i<=n;i++)
        {
            jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    }
}

long long rec(int x)
{
    if(x==0) return 0;
    ql = in[x];
    qr = ou[x];
    Node beg = query(1,1,n);
    if(beg.ch==0) return 0;
    long long ans = 0;
    for(int nb:g[beg.num])
    {
        if(nb==jump[beg.num][0]) continue;
        ql = in[nb];
        qr = ou[nb];
        int xi = beg.num;
        int yi = query(1,1,n).num;
        long long raz = dist(xi,yi);
        ans = max(ans,rec(nb)+raz);
    }
    ql = in[beg.num];
    qr = ou[beg.num];
    update(1,1,n);
    ql = in[x];
    qr = ou[x];
    int xi = beg.num;
    int yi = query(1,1,n).num;
    long long raz = dist(xi,yi);
    ans = max(ans,rec(x)+raz);
    return ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	read();
	pre();
	cout << rec(1) << endl;
return 0;
}

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