Submission #991495

#	Time	Username	Problem	Language	Result	Execution time	Memory
991495		12345678	Construction of Highway (JOI18_construction)	C++17	100 / 100	314 ms	96124 KiB

construction

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;

ll n, lv[nx], a[nx], b[nx], sz[nx], pa[nx], h[nx], lvl[nx], res[nx], t;
vector<ll> d[nx];
map<ll, ll> mp;

struct range
{
    ll l, r, v;
    range(ll l=0, ll r=0, ll v=0): l(l), r(r), v(v){}
};
stack<range> s[nx];

struct fenwick
{
    ll d[nx];
    void update(int i, ll vl)
    {
        while (i<nx) d[i]+=vl, i+=(i&-i);
    }
    ll query(int i)
    {
        ll res=0;
        while (i>0) res+=d[i], i-=(i&-i);
        return res;
    }
} f;

void dfs(int u, int p)
{
    sz[u]=1;
    for (auto v:d[u]) if (v!=p) dfs(v, u), sz[u]+=sz[v];
}

void hld(int u, int p, int hd)
{
    h[u]=hd;
    pa[u]=p;
    lvl[u]=(p!=-1)?(lvl[p]+1):1;
    pair<int, int> hv;
    for (auto v:d[u]) if (v!=p) hv=max(hv, {sz[v], v});
    if (hv.first) hld(hv.second, u, hd);
    for (auto v:d[u]) if (v!=p&&v!=hv.second) hld(v, u, v);
}

void update(int idx)
{
    ll u=idx;
    vector<range> v;
    while (u!=-1)
    {
        vector<range> tmp;
        while (!s[h[u]].empty()&&s[h[u]].top().r<=lvl[u]) tmp.push_back(s[h[u]].top()), s[h[u]].pop();
        if (!s[h[u]].empty()&&s[h[u]].top().l<=lvl[u]) tmp.push_back(range(s[h[u]].top().l, lvl[u], s[h[u]].top().v)), s[h[u]].top().l=lvl[u]+1;
        s[h[u]].push(range(lvl[h[u]], lvl[u], lv[idx]));
        u=h[u];
        u=pa[u];
        while (!tmp.empty()) v.push_back(tmp.back()), tmp.pop_back();
    }
    //cout<<"range "<<idx<<'\n';
    //for (auto x:v) cout<<x.l<<' '<<x.r<<' '<<x.v<<'\n';
    for (auto x:v) f.update(x.v, x.r-x.l+1), res[idx]+=f.query(x.v-1)*(x.r-x.l+1);
    for (auto x:v) f.update(x.v, -(x.r-x.l+1));
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>lv[i], mp[lv[i]]=0;
    for (auto &[x, y]:mp) y=++t;
    for (int i=1; i<=n; i++) lv[i]=mp[lv[i]];
    for (int i=1; i<n; i++) cin>>a[i]>>b[i], d[a[i]].push_back(b[i]), d[b[i]].push_back(a[i]);
    dfs(1, 1);
    hld(1, -1, 1);
    //for (int i=1; i<=n; i++) cout<<i<<' '<<pa[i]<<' '<<h[i]<<'\n';
    update(1);
    for (int i=1; i<n; i++) update(b[i]);
    for (int i=1; i<n; i++) cout<<res[b[i]]<<'\n';
}

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