Submission #965433

#	Time	Username	Problem	Language	Result	Execution time	Memory
965433		12345678	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	606 ms	119512 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=2e5+5, inf=1e6, kx=18;

ll n, a[nx], u, v, in[nx], out[nx], rin[nx], t, rt, used[nx], pa[nx][kx], dp[nx], cnt, k[nx], lvl[nx];
vector<ll> d[nx], c[nx];

struct node
{
    ll mx, idx, lz;
    node(): mx(0), idx(0), lz(0){}
    node(ll mx, ll idx, ll lz): mx(mx), idx(idx), lz(lz){}
    friend node operator+(const node &a, const node &b)
    {
        if (a.mx>b.mx) return a;
        else return b;
    }
};

struct segtree
{
    node d[4*nx];
    void pushlz(ll l, ll r, ll i)
    {
        d[i].mx+=d[i].lz;
        ll md=(l+r)/2;
        if (l!=r) d[2*i].lz+=d[i].lz, d[2*i+1].lz+=d[i].lz;
        d[i].lz=0;
    }
    void build(ll l, ll r, ll i)
    {
        if (l==r) return d[i]=node(k[l], l, 0), void();
        ll md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=d[2*i]+d[2*i+1];
    }
    void update(ll l, ll r, ll i, ll ql, ll qr, ll vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return d[i].lz+=vl, pushlz(l, r, i), void();
        ll md=(l+r)/2;
        update(l, md, 2*i, ql ,qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    void show(int l, int r, int i)
    {
        pushlz(l, r, i);
        cout<<"debugseg "<<l<<' '<<r<<' '<<d[i].mx<<' '<<d[i].idx<<'\n';
        if (l==r) return;
        int md=(l+r)/2; 
        show(l, md, 2*i);
        show(md+1, r, 2*i+1);
        d[i]=d[2*i]+d[2*i+1];
    }
} s;
 
void dfs(ll u, ll p)
{
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    in[u]=++t;
    rin[t]=u;
    for (auto v:d[u]) if (v!=p) dfs(v, u);
    out[u]=t;
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return v;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

ll dist(int u, int v)
{
    return lvl[u]+lvl[v]-2*lvl[lca(u, v)];
}

void updateoutrange(ll l, ll r, ll vl)
{
    if (l!=1) s.update(1, n, 1, 1, l-1, vl);
    if (r!=n) s.update(1, n, 1, r+1, n, vl);
}

void solve(ll u)
{
    used[u]=1;
    if (u!=pa[u][0]&&!used[pa[u][0]])
    {
        s.update(1, n, 1, in[u], out[u], -inf);
        c[u].push_back(rin[s.d[1].idx]);
        solve(rin[s.d[1].idx]);
        s.update(1, n, 1, in[u], out[u], inf);
    }
    for (auto v:d[u])
    {
        if (used[v]) continue;
        updateoutrange(in[v], out[v], -inf);
        //cout<<"edge "<<u<<' '<<v<<' '<<in[v]<<' '<<out[v]<<'\n';
        //s.show(1, n, 1);
        c[u].push_back(rin[s.d[1].idx]);
        solve(rin[s.d[1].idx]);
        //cout<<"debug  "<<u<<' '<<s.d[1].idx<<'\n';
        updateoutrange(in[v], out[v], inf);
    }
}

void dfs2(int u)
{
    for (auto v:c[u]) dfs2(v), dp[u]=max(dp[u], dp[v]+dist(u, v));
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (ll i=1; i<=n; i++) cin>>a[i];
    for (int i=1; i<=n; i++) if (a[i]==n) rt=i;
    for (ll i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    dfs(rt, rt);
    for (int i=1; i<=n; i++) k[in[i]]=a[i];
    s.build(1, n, 1);
    solve(rt);
    dfs2(rt);
    cout<<dp[rt];
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::pushlz(long long int, long long int, long long int)':
Main.cpp:30:12: warning: unused variable 'md' [-Wunused-variable]
   30 |         ll md=(l+r)/2;
      |            ^~

• 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