Submission #1005052

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1005052	2024-06-22T06:44:29 Z	amirhoseinfar1385	Nestabilnost (COI23_nestabilnost)	C++17	61 / 100	1441 ms	179580 KB

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,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	25 ms	71516 KB	Output is correct
2	Correct	26 ms	71516 KB	Output is correct
3	Correct	26 ms	71452 KB	Output is correct
4	Correct	25 ms	71512 KB	Output is correct
5	Correct	25 ms	71516 KB	Output is correct
6	Correct	26 ms	71608 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1139 ms	170580 KB	Output is correct
2	Correct	826 ms	170580 KB	Output is correct
3	Correct	874 ms	170656 KB	Output is correct
4	Correct	1242 ms	179580 KB	Output is correct
5	Correct	990 ms	170628 KB	Output is correct
6	Correct	963 ms	170580 KB	Output is correct
7	Correct	998 ms	170568 KB	Output is correct
8	Correct	932 ms	170832 KB	Output is correct
9	Correct	1014 ms	172868 KB	Output is correct

Subtask #3

7.0 / 7.0

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

Subtask #4

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	71516 KB	Output is correct
2	Correct	26 ms	71516 KB	Output is correct
3	Correct	26 ms	71452 KB	Output is correct
4	Correct	25 ms	71512 KB	Output is correct
5	Correct	25 ms	71516 KB	Output is correct
6	Correct	26 ms	71608 KB	Output is correct
7	Correct	11 ms	69720 KB	Output is correct
8	Correct	12 ms	69724 KB	Output is correct
9	Correct	11 ms	69976 KB	Output is correct
10	Correct	12 ms	69724 KB	Output is correct
11	Correct	11 ms	69720 KB	Output is correct
12	Correct	11 ms	69724 KB	Output is correct
13	Correct	10 ms	69980 KB	Output is correct
14	Correct	30 ms	70512 KB	Output is correct
15	Correct	29 ms	70748 KB	Output is correct
16	Correct	30 ms	70720 KB	Output is correct
17	Correct	31 ms	70492 KB	Output is correct
18	Correct	30 ms	70740 KB	Output is correct
19	Correct	30 ms	71008 KB	Output is correct
20	Correct	23 ms	70336 KB	Output is correct
21	Correct	25 ms	70360 KB	Output is correct
22	Correct	24 ms	70304 KB	Output is correct
23	Correct	24 ms	70480 KB	Output is correct
24	Correct	27 ms	70744 KB	Output is correct
25	Correct	28 ms	70740 KB	Output is correct
26	Correct	31 ms	70736 KB	Output is correct
27	Correct	30 ms	70980 KB	Output is correct

Subtask #5

0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	71516 KB	Output is correct
2	Correct	26 ms	71516 KB	Output is correct
3	Correct	26 ms	71452 KB	Output is correct
4	Correct	25 ms	71512 KB	Output is correct
5	Correct	25 ms	71516 KB	Output is correct
6	Correct	26 ms	71608 KB	Output is correct
7	Correct	1139 ms	170580 KB	Output is correct
8	Correct	826 ms	170580 KB	Output is correct
9	Correct	874 ms	170656 KB	Output is correct
10	Correct	1242 ms	179580 KB	Output is correct
11	Correct	990 ms	170628 KB	Output is correct
12	Correct	963 ms	170580 KB	Output is correct
13	Correct	998 ms	170568 KB	Output is correct
14	Correct	932 ms	170832 KB	Output is correct
15	Correct	1014 ms	172868 KB	Output is correct
16	Correct	11 ms	69720 KB	Output is correct
17	Correct	12 ms	69724 KB	Output is correct
18	Correct	11 ms	69976 KB	Output is correct
19	Correct	12 ms	69724 KB	Output is correct
20	Correct	11 ms	69720 KB	Output is correct
21	Correct	11 ms	69724 KB	Output is correct
22	Correct	10 ms	69980 KB	Output is correct
23	Correct	30 ms	70512 KB	Output is correct
24	Correct	29 ms	70748 KB	Output is correct
25	Correct	30 ms	70720 KB	Output is correct
26	Correct	31 ms	70492 KB	Output is correct
27	Correct	30 ms	70740 KB	Output is correct
28	Correct	30 ms	71008 KB	Output is correct
29	Correct	23 ms	70336 KB	Output is correct
30	Correct	25 ms	70360 KB	Output is correct
31	Correct	24 ms	70304 KB	Output is correct
32	Correct	24 ms	70480 KB	Output is correct
33	Correct	27 ms	70744 KB	Output is correct
34	Correct	28 ms	70740 KB	Output is correct
35	Correct	31 ms	70736 KB	Output is correct
36	Correct	30 ms	70980 KB	Output is correct
37	Correct	1271 ms	106540 KB	Output is correct
38	Correct	1203 ms	120404 KB	Output is correct
39	Correct	1317 ms	121704 KB	Output is correct
40	Correct	1441 ms	122020 KB	Output is correct
41	Correct	1261 ms	110676 KB	Output is correct
42	Correct	1203 ms	114004 KB	Output is correct
43	Correct	1184 ms	115280 KB	Output is correct
44	Correct	1202 ms	121412 KB	Output is correct
45	Incorrect	1198 ms	141932 KB	Output isn't correct
46	Halted	0 ms	0 KB	-