oj.uz

Submission #1004691

# Submission time Handle Problem Language Result Execution time Memory
1004691 2024-06-21T12:38:09 Z amirhoseinfar1385 Nestabilnost (COI23_nestabilnost) C++17
41 / 100
 1500 ms 179280 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 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);
			if(seg[i].mina>seg[i].aval+w){
				seg[i].mina=seg[i].aval+w;
			seg[i].lazy=0;
			}
			if(l==r){
				return ;
			}
			long long m=(l+r)>>1;
			push((i<<1),l,m,tl,tr,w);
			push((i<<1)^1,m+1,r,tl,tr,w);
			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();
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 71784 KB Output is correct
2 Correct 293 ms 71772 KB Output is correct
3 Correct 265 ms 71828 KB Output is correct
4 Correct 301 ms 71616 KB Output is correct
5 Correct 345 ms 71768 KB Output is correct
6 Correct 288 ms 71792 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1511 ms 179280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 69980 KB Output is correct
2 Correct 12 ms 69812 KB Output is correct
3 Correct 12 ms 69936 KB Output is correct
4 Correct 12 ms 69720 KB Output is correct
5 Correct 12 ms 69980 KB Output is correct
6 Correct 11 ms 69720 KB Output is correct
7 Correct 12 ms 69720 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 71784 KB Output is correct
2 Correct 293 ms 71772 KB Output is correct
3 Correct 265 ms 71828 KB Output is correct
4 Correct 301 ms 71616 KB Output is correct
5 Correct 345 ms 71768 KB Output is correct
6 Correct 288 ms 71792 KB Output is correct
7 Correct 11 ms 69980 KB Output is correct
8 Correct 12 ms 69812 KB Output is correct
9 Correct 12 ms 69936 KB Output is correct
10 Correct 12 ms 69720 KB Output is correct
11 Correct 12 ms 69980 KB Output is correct
12 Correct 11 ms 69720 KB Output is correct
13 Correct 12 ms 69720 KB Output is correct
14 Correct 180 ms 70480 KB Output is correct
15 Correct 166 ms 70736 KB Output is correct
16 Correct 175 ms 70572 KB Output is correct
17 Correct 191 ms 70480 KB Output is correct
18 Correct 220 ms 70740 KB Output is correct
19 Correct 218 ms 70992 KB Output is correct
20 Correct 193 ms 70276 KB Output is correct
21 Correct 194 ms 70300 KB Output is correct
22 Correct 222 ms 70480 KB Output is correct
23 Correct 182 ms 70480 KB Output is correct
24 Correct 200 ms 70832 KB Output is correct
25 Correct 209 ms 70736 KB Output is correct
26 Correct 205 ms 70740 KB Output is correct
27 Correct 213 ms 70868 KB Output is correct

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 71784 KB Output is correct
2 Correct 293 ms 71772 KB Output is correct
3 Correct 265 ms 71828 KB Output is correct
4 Correct 301 ms 71616 KB Output is correct
5 Correct 345 ms 71768 KB Output is correct
6 Correct 288 ms 71792 KB Output is correct
7 Execution timed out 1511 ms 179280 KB Time limit exceeded
8 Halted 0 ms 0 KB -