oj.uz

답안 #784027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
784027 2023-07-15T14:53:13 Z amirhoseinfar1385 Sumtree (INOI20_sumtree) C++17
10 / 100
 3000 ms 289232 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,k;
const long long maxn=2000000+10,maxm=5000000+10;
vector<long long>adj[maxn],child[maxn];
long long par[maxn],val[maxn],link[maxn],fres[maxn],wa[maxn],cnt[maxn],asd,timea=0,high[maxn],fact[maxm],revfact[maxm],mod=1e9+7;
pair<long long,long long>stf[maxn];
 
long long kaf=(1<<19);
 
struct segment{
	set<pair<long long,long long>>seg[(1<<20)];
	pair<long long,long long> get(long long i){
		if(i==0){
			return make_pair(0,0);
		}
		if((long long)seg[i].size()==0){
			return get((i>>1));
		}
		auto x=*seg[i].rbegin();
		return max(get((i>>1)),x);
	}
	void del(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].erase(make_pair(high[w],w));
			return ;
		}
		long long m=(l+r)>>1;
		del((i<<1),l,m,tl,tr,w);
		del((i<<1)^1,m+1,r,tl,tr,w);
	}
 
	void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].insert(make_pair(high[w],w));
			return ;
		}
		long long m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
	}
}segbal;
 
struct segjam{
	long long seg[(1<<20)];
	long long pors(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		long long m=(l+r)>>1;
		long long ret=pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
		return ret;
	}
	void upd(long long i,long long w){
		if(i==0){
			return ;
		}
		seg[i]+=w;
		upd((i>>1),w);
	}
}segjam,segted;
 
struct segres{
	long long seg[(1<<20)];
	segres(){
		for(long long i=kaf;i<(1<<20);i++){
			seg[i]=-1;
		}
		for(long long i=1;i<kaf;i++){
			seg[i]=-1;
		}
	}
	void calc(int i){
		if(seg[(i<<1)]==-1&&seg[(i<<1)^1]==-1){
			seg[i]=-1;
			return ;
		}
		if(seg[(i<<1)]==-1){
			seg[i]=seg[(i<<1)^1];
			return ;
		}
		if(seg[(i<<1)^1]==-1){
			seg[i]=seg[(i<<1)];
			return ;
		}
		seg[i]=1ll*seg[(i<<1)^1]*seg[(i<<1)]%mod;
		return ;
	}
 
	void upd(int i,int l,int r,int tl,int tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			w%=mod;
			seg[i]=w;
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}
 
}res;
 
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){
		p*=m;
		p%=mod;
	}
	return p;
}
 
void aval(){	
	for(int i=0;i<maxn;i++){
		fres[i]=-1;
		val[i]=-1;
	}
	fact[0]=1;
	for(long long i=1;i<maxm;i++){
		fact[i]=1ll*fact[i-1]*i%mod;
	}
	revfact[maxm-1]=mypow(fact[maxm-1],mod-2);
	for(long long i=maxm-2;i>=0;i--){
		revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
	}
}
 
long long c(long long i,long long j){
	if(i<0||j<0||i<j){
		return 0;
	}
	long long ret=1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
	return ret;
}
 
void dfs(long long u,long long para=0){
	cnt[u]=1;
	high[u]=high[para]+1;
	timea++;
	stf[u].first=timea;
	par[u]=para;
	for(auto x:adj[u]){
		if(x!=para){
			child[u].push_back(x);
			dfs(x,u);
			cnt[u]+=cnt[x];
		}
	}
	stf[u].second=timea;
}
 
long long hes(long long a,long long b){
	a++;
	long long ret=c(b+a-1,a-1);	
	return ret;
}
 
void tof(){
	fres[stf[1].first]=hes(n-1,val[1]);
//	res.upd(1,0,kaf-1,stf[1].first,stf[1].first,hes(n-1,val[1]));
//	segbal.upd(1,0,kaf-1,stf[1].first+1,stf[1].second,1);
	link[1]=0;
}
 
int findp(int u,int av){
	if(u==av||val[u]==-1){
		return findp(par[u],av);
	}
	return u;
}

long long porsjam(int u,int av){
	long long ret=0;
	if(u!=av&&val[u]!=-1){
		ret+=val[u];
		return ret;
	}
	for(auto x:child[u]){
		ret+=porsjam(x,av);
	}
	return ret;
}

long long porsted(int u,int av){
	long long ret=0;
	if(u!=av&&val[u]!=-1){
		return ret;
	}
	for(auto x:child[u]){
		ret+=porsjam(x,av);
	}
	ret++;
	return ret;
}

void upd(long long u,long long w){
	wa[u]=w;
	val[u]=w;
//	long long pp=segbal.get(stf[u].first+kaf).second;
	long long pp=findp(u,u);
//	long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	long long jam=porsjam(u,u);
//	long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	long long ted=porsted(u,u);
//	segted.upd(kaf+stf[u].first,ted);
//	segbal.upd(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
//	segjam.upd(kaf+stf[u].first,-jam+w);
//	long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long jamp=porsjam(pp,pp);
//	long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long tedp=porsted(pp,pp);
	long long fake=hes(tedp-1,val[pp]-jamp);
	fres[stf[pp].first]=fake;
//	cout<<u<<" "<<pp<<" "<<jamp<<" "<<val[pp]<<" "<<tedp<<"\n";
//	res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,fake);
	fake=hes(ted-1,val[u]-jam);
	fres[stf[u].first]=fake;
//	res.upd(1,0,kaf-1,stf[u].first,stf[u].first,fake);
}
 
void del(long long u){
//	long long pp=segbal.get(stf[u].first+kaf).second;
	long long pp=findp(u,u);
//	long long jam=segjam.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	long long jam=porsjam(u,u);
//	long long ted=cnt[u]-segted.pors(1,0,kaf-1,stf[u].first+1,stf[u].second);
	long long ted=porsted(u,u);
	val[u]=-1;
//	segted.upd(kaf+stf[u].first,-ted);
//	segbal.del(1,0,kaf-1,stf[u].first+1,stf[u].second,u);
//	segjam.upd(kaf+stf[u].first,+jam-wa[u]);
//	long long jamp=segjam.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long jamp=porsjam(pp,pp);
//	long long tedp=cnt[pp]-segted.pors(1,0,kaf-1,stf[pp].first+1,stf[pp].second);
	long long tedp=porsted(pp,pp);
	long long fake=hes(tedp-1,val[pp]-jamp);
	fres[stf[pp].first]=fake;
	fres[stf[u].first]=-1;
//	res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,-1);
//	res.upd(1,0,kaf-1,stf[pp].first,stf[pp].first,fake);
//	res.upd(1,0,kaf-1,stf[u].first,stf[u].first,-1);
//	val[u]=-1;
}
 
void calres(){
	long long ret=1;
	for(int i=stf[1].first;i<=stf[1].second;i++){
//		cout<<i<<" asd "<<fres[i]<<"\n";
		if(fres[i]==-1){
			continue;
		}
		ret*=fres[i];
		ret%=mod;
	}
	cout<<ret<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	aval();
	cin>>n>>k;
	for(long long i=0;i<n-1;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1);
	segjam.upd(stf[1].first+kaf,k);
	val[1]=k;
	tof();
	long long q;
	cin>>q;
	asd=1;
//	cout<<res.seg[1]<<"\n";
	calres();
	for(;asd<=q;asd++){
		long long qq;
		cin>>qq;
		if(qq==1){
			long long u,w;
			cin>>u>>w;
			upd(u,w);
		}
		else{
			long long u;
			cin>>u;
			del(u);
		}
//		cout<<res.seg[1]<<"\n";
		calres();
	}
}

Compilation message

Main.cpp: In function 'void del(long long int)':
Main.cpp:242:12: warning: unused variable 'jam' [-Wunused-variable]
  242 |  long long jam=porsjam(u,u);
      |            ^~~
Main.cpp:244:12: warning: unused variable 'ted' [-Wunused-variable]
  244 |  long long ted=porsted(u,u);
      |            ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 329 ms 288392 KB Output is correct
2 Correct 310 ms 288336 KB Output is correct
3 Correct 288 ms 288428 KB Output is correct
4 Correct 285 ms 288368 KB Output is correct
5 Correct 268 ms 285584 KB Output is correct
6 Correct 192 ms 261812 KB Output is correct
7 Correct 191 ms 261616 KB Output is correct
8 Correct 197 ms 261652 KB Output is correct
9 Correct 291 ms 280400 KB Output is correct
10 Correct 311 ms 280372 KB Output is correct
11 Correct 296 ms 280408 KB Output is correct
12 Correct 310 ms 279372 KB Output is correct
13 Correct 306 ms 286596 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3073 ms 281532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 329 ms 288392 KB Output is correct
2 Correct 310 ms 288336 KB Output is correct
3 Correct 288 ms 288428 KB Output is correct
4 Correct 285 ms 288368 KB Output is correct
5 Correct 268 ms 285584 KB Output is correct
6 Correct 192 ms 261812 KB Output is correct
7 Correct 191 ms 261616 KB Output is correct
8 Correct 197 ms 261652 KB Output is correct
9 Correct 291 ms 280400 KB Output is correct
10 Correct 311 ms 280372 KB Output is correct
11 Correct 296 ms 280408 KB Output is correct
12 Correct 310 ms 279372 KB Output is correct
13 Correct 306 ms 286596 KB Output is correct
14 Incorrect 189 ms 261344 KB Output isn't correct
15 Halted 0 ms 0 KB -