Submission #1004432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004432		amirhoseinfar1385	Nestabilnost (COI23_nestabilnost)	C++17	0 / 100	515 ms	181840 KiB

code1

#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;
		node(){
			mina=0;
			lazy=0;
			vis=0;
			aval=0;
		}
	};
	node seg[(1<<(lg+1))];
	void ins(long long i,long long w){
		seg[kaf+i].mina=w;
		seg[kaf+i].aval=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);
	}
	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;
	}
	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;
		}
		if(l==r){
			return ;
		}
		int m=(l+r)>>1;
		clear((i<<1),l,m,tl,tr);
		clear((i<<1)^1,m+1,r,tl,tr);
	}
}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){
	//	adj[u].erase(find(adj[u].begin(),adj[u].end(),par));
		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){
	//cout<<u<<endl;
	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;
			continue;
		}
		ret+=re;
		if(all[v]==all[u]+1){
			allind[v].insert(all[v]+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){
			while(tof.front()<=all[v]){
				tof.pop_front();
			}
			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);
			tof.clear();
			tof.push_back(all[u]+1);
			tof.push_back(all[u]+2);
		}
		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-=re;
			if(w>=0){
				continue;
			}
			alle.push_back(make_pair(make_pair(tof[i],tof[i+1]-1),w));
		}
		seg.clear();
	}
	//cout<<"ha: "<<u<<endl;
	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);
	//cout<<"bar: "<<u<<endl;
	if(all[v]!=0&&all[v]-1!=all[u]){
		mainres+=re;
		seg.clear();
	}else{
		swap(allind[u],allind[v]);
	//	ret+=re;
	//	if(u==5){
	//		//cout<<"tagh: "<<u<<" "<<re<<" "<<seg.getmin(1,0,kaf-1,3,3)<<endl;
	//	}
	//	seg.upd(1,0,kaf-1,1,n,-re);
	//	if(u==5){
	//		//cout<<"tagh: "<<u<<" "<<re<<" "<<seg.getmin(1,0,kaf-1,3,3)<<endl;
	//	}
		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);
			allind[u].insert(all[v]+1);
			while((*allind[u].begin())<=all[v]){
				allind[u].erase((*allind[u].begin()));
			}
		}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);
			allind[u].clear();
			allind[u].insert(all[u]+1);
			allind[u].insert(all[u]+2);
		}
	}
	//cout<<"hey1: "<<seg.getmin(1,0,kaf-1,1,3)<<endl;
	for(auto x:alle){
		allind[u].insert(x.first.first);
		seg.upd(1,0,kaf-1,x.first.first,x.first.second,x.second);
		if(u==1){
			//cout<<"chy: "<<x.first.first<<" "<<x.first.second<<" "<<x.second<<endl;
		}
	}
	//cout<<"hey2: "<<seg.getmin(1,0,kaf-1,1,3)<<endl;
	//cout<<"ghablret: "<<ret<<endl;
	ret+=seg.getmin(1,0,kaf-1,all[u]+1,n);
	//cout<<"ret: "<<u<<" "<<ret<<endl;
	return ret;
}

void solve(){
	mainres+=dfs(1);
	cout<<mainres<<"\n";
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	vorod();
	pre();
	solve();
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 20
• Subtask 3: 0 / 7
• Subtask 4: 0 / 22
• Subtask 5: 0 / 39