Submission #785780

#	Time	Username	Problem	Language	Result	Execution time	Memory
785780		winter0101	Construction of Highway (JOI18_construction)	C++14	100 / 100	329 ms	32728 KiB

construction

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=1e5+9;
int c[maxn];
vector<int>a[maxn];
int bit[maxn];
int n;
void add(int pos,int val){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
int get(int pos){
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
pii b[maxn];
int head[maxn];
int sub[maxn];
int gr[maxn];
int p[maxn];
void dfs(int u,int par){
sub[u]=1;
p[u]=par;
for (auto &v:a[u]){
    if (v==par)continue;
    dfs(v,u);
    sub[u]+=sub[v];
    if (a[u][0]==par||sub[a[u][0]]<sub[v]){
        swap(v,a[u][0]);
    }
}
}
int tme=0,cnt=1;
int pos[maxn];
void hld(int u,int par,int h){
head[u]=h;
gr[u]=cnt;
pos[u]=++tme;
if (a[u][0]==par)return;
hld(a[u][0],u,h);
for (auto v:a[u]){
    if (v==a[u][0]||v==par)continue;
    cnt++;
    hld(v,u,v);
}
}
struct line{
int l,r,val;
bool operator < (const line &p1)const {
return l<p1.l;
}
};
multiset<line>nw[maxn];
multiset<line>::iterator it;
long long addpath(int u,int val){
vector<pii>needtoerase;
int began=u;
long long ans=0;
while (u!=0){
    line tmp;
    tmp.l=pos[head[u]],tmp.r=pos[u],tmp.val=val;
    if (!nw[gr[u]].empty()){
        vector<pii>xoa;
        while (!nw[gr[u]].empty()){
            it=nw[gr[u]].begin();
            auto t=(*it);
            if (t.l>tmp.r)break;
            if (t.r<=tmp.r){
                xoa.pb({t.r-t.l+1,t.val});
                nw[gr[u]].erase(it);
                continue;
            }
            //tmp.l<=t.l<=tmp.r<=t.r
            auto copyt=t;
            copyt.l=tmp.r+1;
            nw[gr[u]].erase(it);
            nw[gr[u]].insert(copyt);
            t.r=tmp.r;
            xoa.pb({t.r-t.l+1,t.val});
        }
        reverse(all(xoa));
        for (auto v:xoa){
            needtoerase.pb(v);
            long long bonus=1ll*v.fi*get(v.se-1);
            add(v.se,v.fi);
            ans+=bonus;
        }
    }
    nw[gr[u]].insert(tmp);
    u=p[head[u]];
}
for (auto v:needtoerase){
    add(v.se,-v.fi);
    //cout<<began<<" "<<v.fi<<" "<<v.se<<'\n';
}
return ans;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen(".OUT","w",stdout);
    cin>>n;
    vector<int>nen;
    nen.pb(0);
    map<int,int>nenso;
    for1(i,1,n){
    cin>>c[i];
    nen.pb(c[i]);
    }
    sort(all(nen));
    for1(i,1,sz(nen)-1){
    if (nen[i]==nen[i-1])continue;
    nenso[nen[i]]=nenso[nen[i-1]]+1;
    }
    for1(i,1,n){
    c[i]=nenso[c[i]];
    }
    for1(i,1,n-1){
    cin>>b[i].fi>>b[i].se;
    a[b[i].fi].pb(b[i].se);
    a[b[i].se].pb(b[i].fi);
    }
    dfs(1,0);
    hld(1,0,1);
    addpath(1,c[1]);
    for1(i,1,n-1){
    cout<<addpath(b[i].se,c[b[i].se])<<'\n';
    }
}

Compilation message (stderr)

construction.cpp: In function 'long long int addpath(int, int)':
construction.cpp:71:5: warning: unused variable 'began' [-Wunused-variable]
   71 | int began=u;
      |     ^~~~~

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