Submission #967349

#	Time	Username	Problem	Language	Result	Execution time	Memory
967349		Tuanlinh123	Construction of Highway (JOI18_construction)	C++17	100 / 100	417 ms	20760 KiB

construction

#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=100005;
vector <pll> edges;
vector <ll> A[maxn];
ll a[maxn], h[maxn], dep[maxn];
ll Time, tin[maxn], tout[maxn], pa[maxn];

void dfs(ll u)
{
    tin[u]=++Time;
    for (ll v:A[u])
        if (v!=pa[u])
            dep[v]=dep[u]+1, pa[v]=u, dfs(v);
    tout[u]=Time;
}

namespace SegTree
{
    ll n;
    pll St[maxn*4];
    void init(ll sz){n=sz;}

    void update(ll i, ll Start, ll End, ll idx, pll v)
    {
        if (Start==End) {St[i]=v; return;}
        ll mid=(Start+End)/2;
        if (mid>=idx) update(i*2, Start, mid, idx, v);
        else update(i*2+1, mid+1, End, idx, v);
        St[i]=max(St[i*2], St[i*2+1]);
    }
    void update(ll idx, pll v) {update(1, 1, n, idx, v);}

    pll query(ll i, ll Start, ll End, ll l, ll r)
    {
        if (Start>r || End<l) return {0, 0};
        if (Start>=l && End<=r) return St[i];
        ll mid=(Start+End)/2;
        if (mid<l) return query(i*2+1, mid+1, End, l, r);
        if (mid+1>r) return query(i*2, Start, mid, l, r);
        return max(query(i*2, Start, mid, l, r), query(i*2+1, mid+1, End, l, r));
    }
    pll query(ll l, ll r){return query(1, 1, n, l, r);}
}

struct BIT
{
    ll n;
    vector <ll> bit;
    BIT (ll n): n(n){bit.assign(n+1, 0);}

    void update(ll i, ll val)
    {
        for (; i<=n; i+=i&(-i))
            bit[i]+=val;
    }

    ll query(ll l, ll r)
    {
        ll ans=0; l--;
        for (; r; r-=r&(-r)) ans+=bit[r];
        for (; l; l-=l&(-l)) ans-=bit[l];
        return ans;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n; SegTree::init(n);
    for (ll i=1; i<=n; i++) cin >> a[i], h[i]=1;
    edges.resize(n-1);
    for (auto &[u, v]:edges) 
        cin >> u >> v, A[u].pb(v), A[v].pb(u);
    dfs(1), SegTree::update(tin[1], {0, 1}), h[1]=1;
    for (ll i=1; i<=n; i++)
    {
        for (ll &j:A[i]) if (j==pa[i])
            {swap(j, A[i].back()), A[i].pop_back(); break;}
        sort(A[i].begin(), A[i].end(), [&](ll a, ll b){return tin[a]<tin[b];});
    }
    for (ll i=0; i<sz(edges); i++)
    {
        ll U=edges[i].fi, V=edges[i].se, crr=U;
        vector <ll> v;
        vector <pll> num;
        while (crr)
        {
            ll x=SegTree::query(tin[crr], tout[crr]).se, top=h[x];
            if (x!=crr)
            {
                ll p=upper_bound(A[crr].begin(), A[crr].end(), x, [&](ll a, ll b){return tin[a]<tin[b];})-A[crr].begin();
                h[x]=A[crr][p-1];
            }
            num.pb({dep[crr]-dep[top]+1, a[x]}), v.pb(a[x]), crr=pa[top];
        }
        SegTree::update(tin[V], {i+1, V});
        sort(v.begin(), v.end());
        v.resize(unique(v.begin(), v.end())-v.begin());
        ll k=sz(v), ans=0;
        BIT B(k);
        for (auto [cnt, x]:num)
        {
            x=lower_bound(v.begin(), v.end(), x)-v.begin()+1;
            ans+=B.query(1, x-1)*cnt, B.update(x, cnt);
        }
        cout << ans << "\n";
    }

}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84