제출 #1004677

#제출 시각아이디문제언어결과실행 시간메모리
1004677amirhoseinfar1385Nestabilnost (COI23_nestabilnost)C++17
0 / 100
869 ms165716 KiB
#include<bits/stdc++.h> using namespace std; const long long maxn=300000+10,lg=19,kaf=(1<<lg); vector<long long>adj[maxn]; long long sz[maxn],all[maxn],wa[maxn],n,inf=1e16,inf2=1e13; struct segment{ struct node{ long long mina,lazy,vis,aval,asl; node(){ mina=0; lazy=0; vis=0; aval=0; asl=inf; } }; long long fen[maxn]; node seg[(1<<(lg+1))]; void ins(long long i,long long w){ seg[kaf+i].mina=w; seg[kaf+i].aval=w; fen[i]=w; } void build(){ for(long long i=kaf-1;i>=1;i--){ seg[i].mina=min(seg[(i<<1)].mina,seg[(i<<1)^1].mina); seg[i].aval=seg[i].mina; } } void calc(long long i){ seg[i].vis=1; if(i>=kaf){ seg[i].mina+=seg[i].lazy; seg[i].lazy=0; return ; } seg[i].mina=min(seg[(i<<1)].mina+seg[(i<<1)].lazy,seg[(i<<1)^1].lazy+seg[(i<<1)^1].mina); seg[i].mina=min(seg[i].mina,min(seg[(i<<1)].aval+seg[(i<<1)^1].asl,seg[(i<<1)^1].aval+seg[(i<<1)^1].asl)); } void shift(long long i){ seg[i].vis=1; if(i>=kaf){ return ; } seg[(i<<1)].vis=seg[(i<<1)^1].vis=1; seg[(i<<1)].lazy+=seg[i].lazy; seg[(i<<1)^1].lazy+=seg[i].lazy; seg[i].lazy=0; seg[(i<<1)].asl=min(seg[(i<<1)].asl,seg[i].asl); seg[(i<<1)^1].asl=min(seg[(i<<1)^1].asl,seg[i].asl); seg[i].asl=inf; } void push(long long i,long long l,long long r,long long tl,long long tr,long long w){ if(l>r||l>tr||r<tl||tl>tr){ return ; } if(l>=tl&&r<=tr){ seg[i].asl=min(seg[i].asl,w); shift(i); calc(i); return ; } shift(i); long long m=(l+r)>>1; push((i<<1),l,m,tl,tr,w); push((i<<1)^1,m+1,r,tl,tr,w); calc(i); } void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){ if(l>r||l>tr||r<tl||tl>tr){ return ; } if(l>=tl&&r<=tr){ seg[i].lazy+=w; shift(i); calc(i); return ; } shift(i); long long m=(l+r)>>1; upd((i<<1),l,m,tl,tr,w); upd((i<<1)^1,m+1,r,tl,tr,w); calc(i); } long long getmin(long long i,long long l,long long r,long long tl,long long tr){ if(l>r||l>tr||r<tl||tl>tr){ return inf; } shift(i); calc(i); if(l>=tl&&r<=tr){ return seg[i].mina+seg[i].lazy; } long long m=(l+r)>>1; return min(getmin((i<<1),l,m,tl,tr),getmin((i<<1)^1,m+1,r,tl,tr)); } void clear(long long i=1,int l=0,int r=kaf-1,int tl=1,int tr=n+10){ if(l>r||l>tr||r<tl||tl>tr||seg[i].vis==0){ return ; } if(l>=tl&&r<=tr){ seg[i].vis=0; seg[i].mina=seg[i].aval; seg[i].lazy=0; seg[i].asl=inf; }else{ shift(i); } if(l==r){ if(!(l>=tl&&r<=tr)){ calc(i); } return ; } int m=(l+r)>>1; clear((i<<1),l,m,tl,tr); clear((i<<1)^1,m+1,r,tl,tr); if(!(l>=tl&&r<=tr)){ calc(i); } } }seg; bool cmp(long long a,long long b){ return sz[a]>sz[b]; } void predfs(long long u,long long par=-1){ if(par!=-1){ sort(adj[u].begin(),adj[u].end()); adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par)); } sz[u]=1; for(auto x:adj[u]){ predfs(x,u); sz[u]+=sz[x]; } sort(adj[u].begin(),adj[u].end(),cmp); } void vorod(){ cin>>n; for(long long i=1;i<=n;i++){ cin>>all[i]; } for(long long i=1;i<=n;i++){ cin>>wa[i]; } for(long long i=0;i<n-1;i++){ long long u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } } void pre(){ predfs(1); for(long long i=1;i<=n;i++){ seg.ins(i,wa[i]); } seg.build(); } set<long long>allind[maxn]; long long mainres=0; long long dfs(long long u){ long long ret=0; vector<pair<pair<long long,long long>,long long>>alle; for(long long i=1;i<(long long)adj[u].size();i++){ long long v=adj[u][i]; long long re=dfs(v); if(all[v]!=0&&all[v]-1!=all[u]){ mainres+=re; seg.clear(); continue; } allind[v].insert(all[u]+1); allind[v].insert(all[u]+2); allind[v].insert(1); deque<long long>tof; for(auto x:allind[v]){ tof.push_back(x); } tof.push_back(n+1); if(all[v]==all[u]+1){ seg.upd(1,0,kaf-1,1,all[v],inf2); }else{ seg.upd(1,0,kaf-1,1,all[u],inf2); seg.upd(1,0,kaf-1,all[u]+2,n,inf2); } for(long long i=0;i<(long long)tof.size()-1;i++){ if(tof[i+1]==tof[i]){ continue; } long long w=seg.getmin(1,0,kaf-1,tof[i],tof[i])-wa[tof[i]]; w=min(re,w); if(tof[i]<=all[v]){ w=re; } alle.push_back(make_pair(make_pair(tof[i],tof[i+1]-1),w)); } seg.clear(); } if((int)adj[u].size()==0){ return seg.getmin(1,0,kaf-1,all[u]+1,n); } long long v=adj[u][0]; long long re=dfs(v); //wrf: //for(int i=1;i<=n;i++){ // if(seg.fen[i]>re+wa[i]){ // seg.fen[i]=re+wa[i]; // } //} seg.push(1,0,kaf-1,1,n,re); if(all[v]!=0&&all[v]-1!=all[u]){ mainres+=re; seg.clear(); }else{ swap(allind[u],allind[v]); allind[u].insert(all[u]+1); allind[u].insert(all[u]+2); if(all[v]==all[u]+1){ seg.clear(1,0,kaf-1,1,all[v]); seg.upd(1,0,kaf-1,1,all[v],re); }else{ seg.clear(1,0,kaf-1,1,all[u]); seg.clear(1,0,kaf-1,all[u]+2,n); seg.upd(1,0,kaf-1,1,all[u],re); seg.upd(1,0,kaf-1,all[u]+2,n,re); } } for(auto x:alle){ allind[u].insert(x.first.first); allind[u].insert(x.first.second+1); seg.upd(1,0,kaf-1,x.first.first,x.first.second,x.second); } ret+=seg.getmin(1,0,kaf-1,all[u]+1,n); return ret; } void solve(){ mainres+=dfs(1); cout<<mainres<<"\n"; } int main(){ ios::sync_with_stdio(0); cin.tie(0); vorod(); pre(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...