oj.uz

Submission #635982

# Submission time Handle Problem Language Result Execution time Memory
635982 2022-08-27T13:45:35 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 527 ms 117124 KB 
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long countz,tag,res;
	set<pair<long long ,long long>>mn;
	node(){
		countz=res=1;
		tag=0;
	};
};
vector<long long>high;
long long mod=1e9+7;
vector<long long>fact,revfact;
long long n,r;
long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if((y&1)==1){
		p=1ll*m*p;
		p%=mod;
	}
	return p;
}
vector<long long>st;
vector<pair<long long ,long long>>stf;
vector<vector<long long>>adj;
long long rishe=1;
node seg[(1<<20)];

void build(long long i){
	if((i<<1)>=(1<<20)){
		return ;
	}
	build((i<<1));
	build(((i<<1)^1));
	seg[i].countz=seg[(i<<1)].countz+seg[((i<<1)^1)].countz;
}

void aval(long long u=rishe,long long para=0,long long len=0){
	high[u]=len;
	st.push_back(u);
	stf[u].first=st.size()-1;
	for(auto x:adj[u]){
		if(x!=para){
			aval(x,u,len+1);
		}
	}
	stf[u].second=st.size()-1;
}


long long solvecz(long long i,long long nl,long long nr,long long tl,long long tr){
	if(nl>tr||nr<tl){
		return 0;
	}
	if(nl>=tl&&nr<=tr){
	//	cout<<nl<<" asd "<<nr<<" "<<seg[i].countz<<"\n";
		return seg[i].countz;
	}
	long long m=((nl+nr)>>1);
	long long d=solvecz((i<<1),nl,m,tl,tr);
	d+=solvecz(((i<<1)^1),m+1,nr,tl,tr);
	return d;
}

long long solvest(long long i,long long nl,long long nr,long long tl,long long tr){
	if(nl>tr||nr<tl){
		return 0;
	}
	if(nl>=tl&&nr<=tr){
	//	cout<<nl<<" asd "<<nr<<" "<<seg[i].tag<<"\n";
		return seg[i].tag;
	}
	long long m=((nl+nr)>>1);
	long long d=solvest((i<<1),nl,m,tl,tr);
	d+=solvest(((i<<1)^1),m+1,nr,tl,tr);
	return d;
}

void upmn(long long i,long long nl,long long nr,long long tl,long long tr,long long u){
	if(nl>tr||nr<tl){
		return ;
	}
	if(nl>=tl&&nr<=tr){
		seg[i].mn.insert(make_pair(-high[u],u));
		return ;
	}
	long long m=((nl+nr)>>1);
	upmn((i<<1),nl,m,tl,tr,u);
	upmn(((i<<1)^1),m+1,nr,tl,tr,u);
	return ;
}

void upd(long long u){
	if(u==0){
		return ;
	}
	seg[u].res=seg[(u<<1)].res*seg[((u<<1)^1)].res;
	seg[u].res%=mod;
	seg[u].countz=seg[(u<<1)].countz+seg[((u<<1)^1)].countz;
	seg[u].tag=seg[(u<<1)].tag+seg[((u<<1)^1)].tag;
	return upd((u>>1));
}

long long solvepar(long long u){
	if(u==0){
		return -1;
	}
	long long x=solvepar((u>>1));
	if(x==-1){
		if(seg[u].mn.size()==0){
			return -1;
		}
		pair<long long,long long> y=*(seg[u].mn.begin());
		return y.second;
	}
	else{
		if(seg[u].mn.size()==0){
			return x;
		}
		pair<long long,long long> y=*(seg[u].mn.begin());
		if(high[x]>-y.first){
			return x;
		}
		else{
			return y.second;
		}
	}
}

void update(long long u,long long no,long long c=0){
	if(no==1){
		if(stf[u].first==stf[u].second){
			seg[(1<<19)+stf[u].first].tag=c;
			seg[(1<<19)+stf[u].first].res=1;
			seg[(1<<19)+stf[u].first].countz=0;
		}
		else{
			upmn(1,0,(1<<19)-1,stf[u].first+1,stf[u].second,u);
			seg[(1<<19)+stf[u].first].tag=c;
			seg[(1<<19)+stf[u].first].countz=-solvecz(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
			long long x=solvest(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
			if(x>c){
				seg[(1<<19)+stf[u].first].res=0;
			}
			else{
				seg[(1<<19)+stf[u].first].res=fact[c-x+-seg[(1<<19)+stf[u].first].countz];
				seg[(1<<19)+stf[u].first].res*=revfact[-seg[(1<<19)+stf[u].first].countz];
				seg[(1<<19)+stf[u].first].res%=mod;
				seg[(1<<19)+stf[u].first].res*=revfact[c-x];
				seg[(1<<19)+stf[u].first].res%=mod;
			}
	//		cout<<c<<" "<<x<<" "<<seg[(1<<19)+stf[u].first].countz<<"\n";
		}	
		long long fu=stf[u].first;
		fu+=(1<<19);
		fu=(fu>>1);
		upd(fu);
		fu=stf[u].first;
		fu+=(1<<19);
		u=solvepar(fu);
		fu-=(1<<19);
		if(u==-1){
			return ;
		}
		seg[(1<<19)+stf[u].first].tag-=seg[(1<<19)+stf[fu].first].tag;
		c=seg[(1<<19)+stf[u].first].tag;
	//	cout<<" s "<<u<<"\n";
		if(stf[u].first==stf[u].second){
			seg[(1<<19)+stf[u].first].res=1;
			seg[(1<<19)+stf[u].first].countz=0;
		}
		else{
			seg[(1<<19)+stf[u].first].countz=-solvecz(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
			long long x=solvest(1,0,(1<<19)-1,stf[u].first+1,stf[u].second);
			if(x>c){
				seg[(1<<19)+stf[u].first].res=0;
		//		cout<<c<<" "<<x<<"\n";
			}
			else{
				seg[(1<<19)+stf[u].first].res=fact[c-x+-seg[(1<<19)+stf[u].first].countz];
				seg[(1<<19)+stf[u].first].res*=revfact[-seg[(1<<19)+stf[u].first].countz];
				seg[(1<<19)+stf[u].first].res%=mod;
				seg[(1<<19)+stf[u].first].res*=revfact[c-x];
				seg[(1<<19)+stf[u].first].res%=mod;
			}
	//		cout<<c<<" "<<x<<" "<<seg[(1<<19)+stf[u].first].countz<<"\n";
		}	
		fu=stf[u].first;
		fu+=(1<<19);
		fu=(fu>>1);
		upd(fu);
	}
	else{

	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	fact.resize(1e6);
	revfact.resize(1e6);
	fact[0]=revfact[0]=1;
	for(int i=1;i<=5e5;i++){
		fact[i]=fact[i-1]*i;
		fact[i]%=mod;
		revfact[i]=mypow(fact[i],mod-2);
	}
	cin>>n>>r;
	adj.resize(n+1);
	high.resize(n+1);
	stf.resize(n+1);
	for(int i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	build(1);
	aval();
	update(1,1,r);
	long long q;
	cin>>q;
	cout<<seg[1].res<<"\n";
	for(int i=0;i<q;i++){
		long long u;
		cin>>u;
		if(u==1){
			long long v,e;
			cin>>v>>e;
			update(v,1,e);
		}
		else{

		}
		cout<<seg[1].res<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 114660 KB Output is correct
2 Correct 363 ms 114528 KB Output is correct
3 Correct 398 ms 114584 KB Output is correct
4 Correct 375 ms 114532 KB Output is correct
5 Correct 362 ms 110704 KB Output is correct
6 Correct 265 ms 90356 KB Output is correct
7 Correct 255 ms 90040 KB Output is correct
8 Correct 258 ms 90096 KB Output is correct
9 Correct 359 ms 108928 KB Output is correct
10 Correct 370 ms 108788 KB Output is correct
11 Correct 356 ms 108912 KB Output is correct
12 Correct 341 ms 107968 KB Output is correct
13 Correct 337 ms 112820 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 89760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 384 ms 117124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 527 ms 113000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 114660 KB Output is correct
2 Correct 363 ms 114528 KB Output is correct
3 Correct 398 ms 114584 KB Output is correct
4 Correct 375 ms 114532 KB Output is correct
5 Correct 362 ms 110704 KB Output is correct
6 Correct 265 ms 90356 KB Output is correct
7 Correct 255 ms 90040 KB Output is correct
8 Correct 258 ms 90096 KB Output is correct
9 Correct 359 ms 108928 KB Output is correct
10 Correct 370 ms 108788 KB Output is correct
11 Correct 356 ms 108912 KB Output is correct
12 Correct 341 ms 107968 KB Output is correct
13 Correct 337 ms 112820 KB Output is correct
14 Incorrect 258 ms 89760 KB Output isn't correct
15 Halted 0 ms 0 KB -