Submission #1005096

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1005096	2024-06-22T07:10:55 Z	amirhoseinfar1385	Nestabilnost (COI23_nestabilnost)	C++17	61 / 100	1423 ms	179532 KB

code1

#include<bits/stdc++.h>
using namespace std;
const long long maxn=300000+40,lg=19,kaf=(1<<lg);
vector<long long>adj[maxn];
long long sz[maxn],all[maxn],wa[maxn],n,inf=1e17,inf2=1e17;
 
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].aval);
			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+seg[i].aval);
	}
	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=seg[i].asl;
			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;
			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	23 ms	71516 KB	Output is correct
2	Correct	24 ms	71620 KB	Output is correct
3	Correct	36 ms	71512 KB	Output is correct
4	Correct	35 ms	71516 KB	Output is correct
5	Correct	24 ms	71480 KB	Output is correct
6	Correct	28 ms	71516 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1293 ms	170580 KB	Output is correct
2	Correct	926 ms	170624 KB	Output is correct
3	Correct	1016 ms	170576 KB	Output is correct
4	Correct	1308 ms	179532 KB	Output is correct
5	Correct	1008 ms	170576 KB	Output is correct
6	Correct	994 ms	170564 KB	Output is correct
7	Correct	1026 ms	170580 KB	Output is correct
8	Correct	1070 ms	170700 KB	Output is correct
9	Correct	1072 ms	172796 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	69724 KB	Output is correct
2	Correct	11 ms	69976 KB	Output is correct
3	Correct	11 ms	69980 KB	Output is correct
4	Correct	14 ms	69972 KB	Output is correct
5	Correct	11 ms	69724 KB	Output is correct
6	Correct	12 ms	69724 KB	Output is correct
7	Correct	12 ms	69976 KB	Output is correct

Subtask #4

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	71516 KB	Output is correct
2	Correct	24 ms	71620 KB	Output is correct
3	Correct	36 ms	71512 KB	Output is correct
4	Correct	35 ms	71516 KB	Output is correct
5	Correct	24 ms	71480 KB	Output is correct
6	Correct	28 ms	71516 KB	Output is correct
7	Correct	12 ms	69724 KB	Output is correct
8	Correct	11 ms	69976 KB	Output is correct
9	Correct	11 ms	69980 KB	Output is correct
10	Correct	14 ms	69972 KB	Output is correct
11	Correct	11 ms	69724 KB	Output is correct
12	Correct	12 ms	69724 KB	Output is correct
13	Correct	12 ms	69976 KB	Output is correct
14	Correct	29 ms	70484 KB	Output is correct
15	Correct	29 ms	70448 KB	Output is correct
16	Correct	32 ms	70424 KB	Output is correct
17	Correct	34 ms	70420 KB	Output is correct
18	Correct	29 ms	70492 KB	Output is correct
19	Correct	42 ms	70992 KB	Output is correct
20	Correct	24 ms	70248 KB	Output is correct
21	Correct	24 ms	70352 KB	Output is correct
22	Correct	34 ms	70376 KB	Output is correct
23	Correct	24 ms	70344 KB	Output is correct
24	Correct	28 ms	70488 KB	Output is correct
25	Correct	29 ms	70492 KB	Output is correct
26	Correct	29 ms	70740 KB	Output is correct
27	Correct	29 ms	70744 KB	Output is correct

Subtask #5

0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	71516 KB	Output is correct
2	Correct	24 ms	71620 KB	Output is correct
3	Correct	36 ms	71512 KB	Output is correct
4	Correct	35 ms	71516 KB	Output is correct
5	Correct	24 ms	71480 KB	Output is correct
6	Correct	28 ms	71516 KB	Output is correct
7	Correct	1293 ms	170580 KB	Output is correct
8	Correct	926 ms	170624 KB	Output is correct
9	Correct	1016 ms	170576 KB	Output is correct
10	Correct	1308 ms	179532 KB	Output is correct
11	Correct	1008 ms	170576 KB	Output is correct
12	Correct	994 ms	170564 KB	Output is correct
13	Correct	1026 ms	170580 KB	Output is correct
14	Correct	1070 ms	170700 KB	Output is correct
15	Correct	1072 ms	172796 KB	Output is correct
16	Correct	12 ms	69724 KB	Output is correct
17	Correct	11 ms	69976 KB	Output is correct
18	Correct	11 ms	69980 KB	Output is correct
19	Correct	14 ms	69972 KB	Output is correct
20	Correct	11 ms	69724 KB	Output is correct
21	Correct	12 ms	69724 KB	Output is correct
22	Correct	12 ms	69976 KB	Output is correct
23	Correct	29 ms	70484 KB	Output is correct
24	Correct	29 ms	70448 KB	Output is correct
25	Correct	32 ms	70424 KB	Output is correct
26	Correct	34 ms	70420 KB	Output is correct
27	Correct	29 ms	70492 KB	Output is correct
28	Correct	42 ms	70992 KB	Output is correct
29	Correct	24 ms	70248 KB	Output is correct
30	Correct	24 ms	70352 KB	Output is correct
31	Correct	34 ms	70376 KB	Output is correct
32	Correct	24 ms	70344 KB	Output is correct
33	Correct	28 ms	70488 KB	Output is correct
34	Correct	29 ms	70492 KB	Output is correct
35	Correct	29 ms	70740 KB	Output is correct
36	Correct	29 ms	70744 KB	Output is correct
37	Correct	1323 ms	98900 KB	Output is correct
38	Correct	1193 ms	112516 KB	Output is correct
39	Correct	1222 ms	113096 KB	Output is correct
40	Correct	1423 ms	113184 KB	Output is correct
41	Correct	1181 ms	103172 KB	Output is correct
42	Correct	1184 ms	106472 KB	Output is correct
43	Correct	1142 ms	107580 KB	Output is correct
44	Correct	1177 ms	113488 KB	Output is correct
45	Incorrect	1168 ms	134268 KB	Output isn't correct
46	Halted	0 ms	0 KB	-