oj.uz

Submission #1004622

# Submission time Handle Problem Language Result Execution time Memory
1004622 2024-06-21T10:46:06 Z amirhoseinfar1385 Nestabilnost (COI23_nestabilnost) C++17
41 / 100
 1500 ms 333672 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;
		node(){
			mina=0;
			lazy=0;
			vis=0;
			aval=0;
		}
	};
	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;
	}
	void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
		for(int j=tl;j<=tr;j++){
			fen[j]+=w;
		}
		return ;
		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(tl>tr){
			return inf;
		}
		long long mn=fen[tl];
		for(int j=tl+1;j<=tr;j++){
			mn=min(mn,fen[j]);
		}
		return mn;
		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){
		for(int j=tl;j<=tr;j++){
			fen[j]=wa[j];
		}
		return ;
		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){
		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;
		}
		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);
		}
		tof.clear();
		for(int i=1;i<=n+1;i++){
			tof.push_back(i);
		}
		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]);
		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);
		}
	}
	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 57 ms 56140 KB Output is correct
2 Correct 75 ms 56328 KB Output is correct
3 Correct 49 ms 56408 KB Output is correct
4 Correct 62 ms 56312 KB Output is correct
5 Correct 58 ms 56316 KB Output is correct
6 Correct 56 ms 56156 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 54364 KB Output is correct
2 Correct 21 ms 54464 KB Output is correct
3 Correct 23 ms 54360 KB Output is correct
4 Correct 27 ms 54356 KB Output is correct
5 Correct 25 ms 54464 KB Output is correct
6 Correct 20 ms 54364 KB Output is correct
7 Correct 22 ms 54364 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 56140 KB Output is correct
2 Correct 75 ms 56328 KB Output is correct
3 Correct 49 ms 56408 KB Output is correct
4 Correct 62 ms 56312 KB Output is correct
5 Correct 58 ms 56316 KB Output is correct
6 Correct 56 ms 56156 KB Output is correct
7 Correct 21 ms 54364 KB Output is correct
8 Correct 21 ms 54464 KB Output is correct
9 Correct 23 ms 54360 KB Output is correct
10 Correct 27 ms 54356 KB Output is correct
11 Correct 25 ms 54464 KB Output is correct
12 Correct 20 ms 54364 KB Output is correct
13 Correct 22 ms 54364 KB Output is correct
14 Correct 1067 ms 196168 KB Output is correct
15 Correct 966 ms 198080 KB Output is correct
16 Correct 974 ms 197048 KB Output is correct
17 Correct 1044 ms 208544 KB Output is correct
18 Correct 1100 ms 251488 KB Output is correct
19 Correct 1125 ms 333672 KB Output is correct
20 Correct 454 ms 161900 KB Output is correct
21 Correct 477 ms 178176 KB Output is correct
22 Correct 484 ms 175496 KB Output is correct
23 Correct 481 ms 177656 KB Output is correct
24 Correct 750 ms 256436 KB Output is correct
25 Correct 785 ms 269484 KB Output is correct
26 Correct 803 ms 296968 KB Output is correct
27 Correct 881 ms 319596 KB Output is correct

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 56140 KB Output is correct
2 Correct 75 ms 56328 KB Output is correct
3 Correct 49 ms 56408 KB Output is correct
4 Correct 62 ms 56312 KB Output is correct
5 Correct 58 ms 56316 KB Output is correct
6 Correct 56 ms 56156 KB Output is correct
7 Execution timed out 1538 ms 168532 KB Time limit exceeded
8 Halted 0 ms 0 KB -