oj.uz

답안 #947916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
947916 2024-03-17T09:09:33 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 307 ms 279884 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr first
#define sc second
const int mxn=5e5+5,M=1e9+7,kkk=(1<<21);
int n,q,r,st[mxn],fn[mxn],cnt=0,sz[mxn],g[mxn],bbb;
ll ans,fuck[mxn],rfuck[mxn];
vector<int>v[mxn];
ll ferma(ll x){
	ll num=M-2,res=1;
	while(num){
		if(num&1)res=(res*x)%M;
		x=(x*x)%M;
		num/=2;
	}
	return res;
}
void dfs(int z){
	sz[z]=1;
	st[z]=++cnt;
	for(auto i:v[z]){
		if(!st[i]){
			dfs(i);
			sz[z]+=sz[i];
		}
	}
	fn[z]=cnt;
}
void make(){
	fuck[0]=rfuck[0]=1;
	for(int i=1;i<=n+r;i++){
		fuck[i]=(fuck[i-1]*i)%M;
		rfuck[i]=ferma(fuck[i]);
	}
}
ll comb(int x,int y,bool w){
	if(x>y || x<0 || y<0){
		bbb+=(w)?-1:1;
		return 1;
	}
	ll res=fuck[y]*rfuck[x];
	res%=M;
	res*=rfuck[y-x];
	return res%M;
}
struct segment{
	ll val[mxn];
	void up(int id,ll x){
		for(;id<n;id+=id&(-id))
			val[id]+=x;
	}
	ll get(int id){
		ll res=0;
		for(;id>0;id-=id&(-id))
			res+=val[id];
		return res;
	}
	ll get(int L,int R){
		return get(R-1)-get(L-1);
	}
}seg[2];
struct fnd{
	set<int>s[kkk];
	int get(int id,int L,int R,int l,int r){
		if(L==l && R==r)
			return ((s[id].size())?*s[id].rbegin():0);
		int mid=(L+R)/2,res=((s[id].size())?*s[id].rbegin():0),x=0;
		if(l<mid){
			x=get(id*2,L,mid,l,min(r,mid));
		}
		return (x)?x:res;
	}

	void add(int id ,int L,int R,int l,int r,int x,bool y){
		if(L==l && R==r){
			if(y)
				s[id].insert(x);
			else
				s[id].erase(x);
			return;
		}
		int mid=(L+R)/2;
		if(l<mid)
			add(id*2,L,mid,l,min(r,mid),x,y);
		if(r>mid)
			add(id*2+1,mid,R,max(l,mid),r,x,y);
	}
}fnd;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>r;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1);
	make();
	ans=comb(n-1,n+r-1,0);
	seg[0].up(1,n);
	seg[1].up(1,r);
	fnd.add(1,1,n+1,1,n+1,1,1);
	g[1]=r;
	cout<<ans<<'\n';
	cin>>q;
	while(q--){
		int ty,x,y,z;
		cin>>ty;
		if(ty==1){
			cin>>x>>g[x];
			z=fnd.get(1,1,n+1,st[x],fn[x]+1);
			fnd.add(1,1,n+1,st[x],fn[x]+1,st[x],1);
		}
		else{
			cin>>x;
			fnd.add(1,1,n+1,st[x],fn[x]+1,st[x],0);
			 z=fnd.get(1,1,n+1,st[x],fn[x]+1);
		}
		ll v2,v1,t1,t2;
		if(ty==1){
			t1=seg[0].get(st[x]+1,fn[x]+1);
			t2=seg[0].get(st[z]+1,fn[z]+1);

			seg[0].up(st[x],sz[x]-t1);
			seg[0].up(st[z],-sz[x]+t1);

 			v2=seg[1].get(st[z],fn[z]+1);
			ans*=ferma(comb(sz[z]-t2-1,sz[z]-t2+v2-1,1));
			ans%=M;
			
			int sz1=sz[x]-t1;
			int sz2=sz[z]-t2-sz1;

			v1=seg[1].get(st[x]+1,fn[x]+1);

			seg[1].up(st[x],g[x]-v1);
			seg[1].up(st[z],(v1-g[x])*2);
 
			v1=seg[1].get(st[x],fn[x]+1);
			v2=seg[1].get(st[z],fn[z]+1);
 			
			int val1=comb(sz1-1,sz1-1+v1,0);
			int val2=comb(sz2-1,sz2-1+v2,0);
			ans*=val1;
			ans%=M;
			ans*=val2;
			ans%=M;
			
		}
		else{
			
			int sz1=sz[x]-t1;
			int sz2=sz[z]-t2;
 
			ans*=ferma(comb(sz1-1,sz1+v1-1,1));
			ans%=M;
			ans*=ferma(comb(sz2-1,sz2+v2-1,1));
			ans%=M;
 
			seg[0].up(st[x],-sz1);
			seg[0].up(st[z],sz1);
			
			sz2+=sz1;
 
			seg[1].up(st[x],-v1);
			seg[1].up(st[z],v1);
			
			v2=seg[1].get(st[z],fn[z]+1);
			int val1=comb(sz2-1,sz2-1+v2,0);
			ans*=val1;
			ans%=M;
 
		}
		if(bbb){
			cout<<0<<'\n';
		}
		else
			cout<<ans<<'\n';
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:111:12: warning: unused variable 'y' [-Wunused-variable]
  111 |   int ty,x,y,z;
      |            ^
Main.cpp:157:17: warning: 't2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 |    int sz2=sz[z]-t2;
      |            ~~~~~^~~
Main.cpp:156:17: warning: 't1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  156 |    int sz1=sz[x]-t1;
      |            ~~~~~^~~
Main.cpp:51:11: warning: 'v1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |    val[id]+=x;
      |    ~~~~~~~^~~
Main.cpp:123:9: note: 'v1' was declared here
  123 |   ll v2,v1,t1,t2;
      |         ^~
Main.cpp:161:29: warning: 'v2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |    ans*=ferma(comb(sz2-1,sz2+v2-1,1));
      |                          ~~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 136784 KB Output is correct
2 Correct 190 ms 134924 KB Output is correct
3 Correct 170 ms 133740 KB Output is correct
4 Correct 172 ms 136544 KB Output is correct
5 Correct 182 ms 133424 KB Output is correct
6 Correct 87 ms 117232 KB Output is correct
7 Correct 85 ms 116952 KB Output is correct
8 Correct 66 ms 115028 KB Output is correct
9 Correct 168 ms 130900 KB Output is correct
10 Correct 170 ms 131160 KB Output is correct
11 Correct 172 ms 131204 KB Output is correct
12 Correct 150 ms 127056 KB Output is correct
13 Correct 161 ms 135380 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 288 ms 279884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 307 ms 271436 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 136784 KB Output is correct
2 Correct 190 ms 134924 KB Output is correct
3 Correct 170 ms 133740 KB Output is correct
4 Correct 172 ms 136544 KB Output is correct
5 Correct 182 ms 133424 KB Output is correct
6 Correct 87 ms 117232 KB Output is correct
7 Correct 85 ms 116952 KB Output is correct
8 Correct 66 ms 115028 KB Output is correct
9 Correct 168 ms 130900 KB Output is correct
10 Correct 170 ms 131160 KB Output is correct
11 Correct 172 ms 131204 KB Output is correct
12 Correct 150 ms 127056 KB Output is correct
13 Correct 161 ms 135380 KB Output is correct
14 Incorrect 48 ms 112200 KB Output isn't correct
15 Halted 0 ms 0 KB -