oj.uz

Submission #635976

# Submission time Handle Problem Language Result Execution time Memory
635976 2022-08-27T13:42:44 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 515 ms 232552 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[u].tag-=seg[fu].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 382 ms 114528 KB Output is correct
2 Correct 368 ms 114532 KB Output is correct
3 Correct 359 ms 114512 KB Output is correct
4 Correct 366 ms 114496 KB Output is correct
5 Correct 361 ms 110820 KB Output is correct
6 Correct 260 ms 90224 KB Output is correct
7 Correct 249 ms 90060 KB Output is correct
8 Correct 243 ms 90100 KB Output is correct
9 Correct 371 ms 108828 KB Output is correct
10 Correct 361 ms 108816 KB Output is correct
11 Correct 356 ms 108904 KB Output is correct
12 Correct 356 ms 107972 KB Output is correct
13 Correct 351 ms 112880 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 454 ms 232552 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 114528 KB Output is correct
2 Correct 368 ms 114532 KB Output is correct
3 Correct 359 ms 114512 KB Output is correct
4 Correct 366 ms 114496 KB Output is correct
5 Correct 361 ms 110820 KB Output is correct
6 Correct 260 ms 90224 KB Output is correct
7 Correct 249 ms 90060 KB Output is correct
8 Correct 243 ms 90100 KB Output is correct
9 Correct 371 ms 108828 KB Output is correct
10 Correct 361 ms 108816 KB Output is correct
11 Correct 356 ms 108904 KB Output is correct
12 Correct 356 ms 107972 KB Output is correct
13 Correct 351 ms 112880 KB Output is correct
14 Incorrect 250 ms 89864 KB Output isn't correct
15 Halted 0 ms 0 KB -