oj.uz

Submission #1005024

# Submission time Handle Problem Language Result Execution time Memory
1005024 2024-06-22T06:19:00 Z amirhoseinfar1385 Nestabilnost (COI23_nestabilnost) C++17
32 / 100
 708 ms 188344 KB 
#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);
	}
	void calcasl(int i){
		seg[i].vis=1;
		if(i>=kaf){
			seg[i].mina+=seg[i].lazy;
			seg[i].lazy=0;
			seg[i].mina=min(seg[i].mina,seg[i].asl);
			seg[i].asl=inf;
			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;
		calc(i);
		seg[i].mina=min(seg[i].mina,seg[i].asl);
	}
	void shift(long long i){
		if(seg[i].asl==inf){
			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;
			calc(i);
		}else{
			seg[i].vis=seg[(i<<1)].vis=seg[(i<<1)^1].vis=1;
			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;
			calcasl((i<<1));
			calcasl((i<<1)^1);
			seg[(i<<1)].lazy+=seg[i].lazy;
			seg[(i<<1)^1].lazy+=seg[i].lazy;
			seg[i].lazy=0;
			calc(i);
		}
	}
	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){
			shift(i);
			calc(i);
			seg[i].asl=w;
			calcasl(i);
			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){
			shift(i);
			calc(i);
			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;
		}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];
	//	}
	//}
	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();
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 71516 KB Output is correct
2 Correct 21 ms 71724 KB Output is correct
3 Correct 22 ms 71540 KB Output is correct
4 Correct 20 ms 71512 KB Output is correct
5 Correct 20 ms 71516 KB Output is correct
6 Correct 22 ms 71516 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 178316 KB Output is correct
2 Correct 477 ms 178260 KB Output is correct
3 Correct 509 ms 178740 KB Output is correct
4 Correct 678 ms 188344 KB Output is correct
5 Correct 614 ms 178532 KB Output is correct
6 Correct 603 ms 178256 KB Output is correct
7 Correct 587 ms 178240 KB Output is correct
8 Correct 583 ms 178568 KB Output is correct
9 Correct 611 ms 180560 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 69972 KB Output is correct
2 Correct 11 ms 69984 KB Output is correct
3 Correct 11 ms 69980 KB Output is correct
4 Incorrect 11 ms 69740 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 71516 KB Output is correct
2 Correct 21 ms 71724 KB Output is correct
3 Correct 22 ms 71540 KB Output is correct
4 Correct 20 ms 71512 KB Output is correct
5 Correct 20 ms 71516 KB Output is correct
6 Correct 22 ms 71516 KB Output is correct
7 Correct 11 ms 69972 KB Output is correct
8 Correct 11 ms 69984 KB Output is correct
9 Correct 11 ms 69980 KB Output is correct
10 Incorrect 11 ms 69740 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 71516 KB Output is correct
2 Correct 21 ms 71724 KB Output is correct
3 Correct 22 ms 71540 KB Output is correct
4 Correct 20 ms 71512 KB Output is correct
5 Correct 20 ms 71516 KB Output is correct
6 Correct 22 ms 71516 KB Output is correct
7 Correct 708 ms 178316 KB Output is correct
8 Correct 477 ms 178260 KB Output is correct
9 Correct 509 ms 178740 KB Output is correct
10 Correct 678 ms 188344 KB Output is correct
11 Correct 614 ms 178532 KB Output is correct
12 Correct 603 ms 178256 KB Output is correct
13 Correct 587 ms 178240 KB Output is correct
14 Correct 583 ms 178568 KB Output is correct
15 Correct 611 ms 180560 KB Output is correct
16 Correct 11 ms 69972 KB Output is correct
17 Correct 11 ms 69984 KB Output is correct
18 Correct 11 ms 69980 KB Output is correct
19 Incorrect 11 ms 69740 KB Output isn't correct
20 Halted 0 ms 0 KB -