Submission #1223149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223149		AlgorithmWarrior	Construction of Highway (JOI18_construction)	C++20	100 / 100	723 ms	30624 KiB

construction

#include <bits/stdc++.h>

using namespace std;

int const NMAX=100005;
int const LOG=20;
int n;
int v[NMAX];
vector<int>tree[NMAX];
struct edge{
    int u,v;
}edges[NMAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
    for(i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        edges[i]={u,v};
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
}

void normalize(){
    map<int,int>mep;
    int i;
    for(i=1;i<=n;++i)
        mep[v[i]]=0;
    int ind=0;
    for(auto &[orig_val,new_val] : mep)
        new_val=++ind;
    for(i=1;i<=n;++i)
        v[i]=mep[v[i]];
}

int lift[NMAX][LOG];
int subsz[NMAX];
int h[NMAX];

void dfs(int nod){
    int i;
    for(i=1;i<LOG;++i)
        lift[nod][i]=lift[lift[nod][i-1]][i-1];
    subsz[nod]=1;
    for(auto fiu : tree[nod])
        if(fiu!=lift[nod][0]){
            lift[fiu][0]=nod;
            h[fiu]=h[nod]+1;
            dfs(fiu);
            subsz[nod]+=subsz[fiu];
        }
}

int id[NMAX],leader[NMAX];

void hld(int nod){
    static int time=0;
    id[nod]=++time;
    if(!leader[nod])
        leader[nod]=nod;
    int heavy_son=0;
    for(auto fiu : tree[nod])
        if(fiu!=lift[nod][0] && subsz[fiu]>subsz[heavy_son])
            heavy_son=fiu;
    if(heavy_son){
        leader[heavy_son]=leader[nod];
        hld(heavy_son);
        for(auto fiu : tree[nod])
            if(fiu!=lift[nod][0] && fiu!=heavy_son)
                hld(fiu);
    }
}

struct segment_tree{
    int v[4*NMAX];
    void update(int nod,int st,int dr,int a,int b,int val){
        if(a<=st && dr<=b)
            v[nod]=val;
        else{
            if(v[nod]){
               v[2*nod]=v[nod];
               v[2*nod+1]=v[nod];
               v[nod]=0;
            }
            int mij=(st+dr)/2;
            if(a<=mij)
                update(2*nod,st,mij,a,b,val);
            if(b>mij)
                update(2*nod+1,mij+1,dr,a,b,val);
        }
    }
    int query(int nod,int st,int dr,int pos){
        if(v[nod])
            return v[nod];
        if(st==dr)
            return -1;
        int mij=(st+dr)/2;
        if(pos<=mij)
            return query(2*nod,st,mij,pos);
        else
            return query(2*nod+1,mij+1,dr,pos);
    }
}aint;

struct fenwick_tree{
    int v[NMAX];
    int ub(int x){
        return x&(-x);
    }
    void add(int pos,int val){
        while(pos<=n){
            v[pos]+=val;
            pos+=ub(pos);
        }
    }
    int qry(int pos){
        int s=0;
        while(pos){
            s+=v[pos];
            pos-=ub(pos);
        }
        return s;
    }
}aib;

long long process_query(int nod){
    long long ans=0;
    vector<pair<int,int>>upds;
    while(nod){
        int i;
        int anc=nod;
        int tip=aint.query(1,1,n,id[nod]);
        for(i=LOG-1;i>=0;--i)
            if(lift[anc][i] && tip==aint.query(1,1,n,id[lift[anc][i]]))
                anc=lift[anc][i];
        ans+=1LL*(h[nod]-h[anc]+1)*aib.qry(v[tip]-1);
        aib.add(v[tip],h[nod]-h[anc]+1);
        upds.push_back({v[tip],h[nod]-h[anc]+1});
        nod=lift[anc][0];
    }
    for(auto [pos,val] : upds)
        aib.add(pos,-val);
    return ans;
}

void process_update(int nod){
    int orig_nod=nod;
    while(nod){
        aint.update(1,1,n,id[leader[nod]],id[nod],orig_nod);
        nod=lift[leader[nod]][0];
    }
}

void solve(){
    aint.update(1,1,n,1,1,v[1]);
    int i;
    for(i=1;i<n;++i){
        auto [u,v]=edges[i];
        if(v==lift[u][0])
            swap(u,v);
        cout<<process_query(u)<<'\n';
        process_update(v);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    normalize();
    dfs(1);
    hld(1);
    solve();
    return 0;
}

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