oj.uz

Submission #635951

# Submission time Handle Problem Language Result Execution time Memory
635951 2022-08-27T12:45:27 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 468 ms 116972 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){
		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){
		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].countz=seg[(u<<1)].tag+seg[((u<<1)^1)].tag;
	return upd((u>>1));
}

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<<endl;
		}	
		long long fu=stf[u].first;
		fu+=(1<<19);
		fu=(fu>>1);
		upd(fu);
	}
	else{

	}
}

int main(){
	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<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 116964 KB Output is correct
2 Correct 429 ms 116940 KB Output is correct
3 Correct 448 ms 116972 KB Output is correct
4 Correct 435 ms 116932 KB Output is correct
5 Correct 419 ms 113216 KB Output is correct
6 Correct 262 ms 90336 KB Output is correct
7 Correct 256 ms 90076 KB Output is correct
8 Correct 249 ms 90080 KB Output is correct
9 Correct 434 ms 111332 KB Output is correct
10 Correct 457 ms 111228 KB Output is correct
11 Correct 447 ms 111308 KB Output is correct
12 Correct 420 ms 110284 KB Output is correct
13 Correct 442 ms 115036 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 116964 KB Output is correct
2 Correct 429 ms 116940 KB Output is correct
3 Correct 448 ms 116972 KB Output is correct
4 Correct 435 ms 116932 KB Output is correct
5 Correct 419 ms 113216 KB Output is correct
6 Correct 262 ms 90336 KB Output is correct
7 Correct 256 ms 90076 KB Output is correct
8 Correct 249 ms 90080 KB Output is correct
9 Correct 434 ms 111332 KB Output is correct
10 Correct 457 ms 111228 KB Output is correct
11 Correct 447 ms 111308 KB Output is correct
12 Correct 420 ms 110284 KB Output is correct
13 Correct 442 ms 115036 KB Output is correct
14 Incorrect 242 ms 89804 KB Output isn't correct
15 Halted 0 ms 0 KB -