oj.uz

Submission #635988

# Submission time Handle Problem Language Result Execution time Memory
635988 2022-08-27T13:51:49 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 520 ms 125480 KB 
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long countz,tag,res,ftag;
	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){
		seg[(1<<19)+stf[u].first].ftag=c;
		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,ffu=u;
		fu+=(1<<19);
		fu=(fu>>1);
		upd(fu);
		fu=stf[u].first;
		fu+=(1<<19);
		u=solvepar(fu);
		fu=ffu;
		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].ftag;
	//	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 360 ms 122736 KB Output is correct
2 Correct 359 ms 122700 KB Output is correct
3 Correct 394 ms 122740 KB Output is correct
4 Correct 379 ms 122656 KB Output is correct
5 Correct 349 ms 119032 KB Output is correct
6 Correct 250 ms 98416 KB Output is correct
7 Correct 267 ms 98304 KB Output is correct
8 Correct 252 ms 98308 KB Output is correct
9 Correct 367 ms 117108 KB Output is correct
10 Correct 383 ms 117016 KB Output is correct
11 Correct 363 ms 117040 KB Output is correct
12 Correct 393 ms 116188 KB Output is correct
13 Correct 345 ms 121164 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 122736 KB Output is correct
2 Correct 359 ms 122700 KB Output is correct
3 Correct 394 ms 122740 KB Output is correct
4 Correct 379 ms 122656 KB Output is correct
5 Correct 349 ms 119032 KB Output is correct
6 Correct 250 ms 98416 KB Output is correct
7 Correct 267 ms 98304 KB Output is correct
8 Correct 252 ms 98308 KB Output is correct
9 Correct 367 ms 117108 KB Output is correct
10 Correct 383 ms 117016 KB Output is correct
11 Correct 363 ms 117040 KB Output is correct
12 Correct 393 ms 116188 KB Output is correct
13 Correct 345 ms 121164 KB Output is correct
14 Incorrect 253 ms 97980 KB Output isn't correct
15 Halted 0 ms 0 KB -