oj.uz

답안 #635984

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
635984 2022-08-27T13:47:03 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 500 ms 117084 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,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].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

# 결과 실행 시간 메모리 Grader output
1 Correct 357 ms 114428 KB Output is correct
2 Correct 345 ms 114492 KB Output is correct
3 Correct 352 ms 114532 KB Output is correct
4 Correct 351 ms 114540 KB Output is correct
5 Correct 340 ms 110912 KB Output is correct
6 Correct 252 ms 90220 KB Output is correct
7 Correct 253 ms 90096 KB Output is correct
8 Correct 242 ms 90112 KB Output is correct
9 Correct 345 ms 108908 KB Output is correct
10 Correct 355 ms 108840 KB Output is correct
11 Correct 345 ms 108900 KB Output is correct
12 Correct 340 ms 108060 KB Output is correct
13 Correct 329 ms 112868 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 240 ms 89812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 393 ms 117084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 500 ms 112932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 357 ms 114428 KB Output is correct
2 Correct 345 ms 114492 KB Output is correct
3 Correct 352 ms 114532 KB Output is correct
4 Correct 351 ms 114540 KB Output is correct
5 Correct 340 ms 110912 KB Output is correct
6 Correct 252 ms 90220 KB Output is correct
7 Correct 253 ms 90096 KB Output is correct
8 Correct 242 ms 90112 KB Output is correct
9 Correct 345 ms 108908 KB Output is correct
10 Correct 355 ms 108840 KB Output is correct
11 Correct 345 ms 108900 KB Output is correct
12 Correct 340 ms 108060 KB Output is correct
13 Correct 329 ms 112868 KB Output is correct
14 Incorrect 240 ms 89812 KB Output isn't correct
15 Halted 0 ms 0 KB -