oj.uz

Submission #1036752

# Submission time Handle Problem Language Result Execution time Memory
1036752 2024-07-27T16:20:09 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 382 ms 142368 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);
ll n,q,r,st[mxn],fn[mxn],cnt=0,sz[mxn],g[mxn],bbb;
ll ans,fuck[mxn*2],rfuck[mxn*2];
vector<ll>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>>=1;
	}
	return res;
}
void dfs(ll 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(ll i=1;i<=n+r;i++){
		fuck[i]=(fuck[i-1]*i)%M;
		rfuck[i]=ferma(fuck[i]);
	}
}
ll comb(ll x,ll y,bool w){
	if(x>y){
		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[kkk];
	void up(ll id,ll L,ll R,ll l,ll x){
		if(L+1==R){
			val[id]=x;
			return;
		}
		ll mid=(L+R)/2;
		if(l<mid)
			up(id*2,L,mid,l,x);
		else
			up(id*2+1,mid,R,l,x);
		val[id]=val[id*2]+val[id*2+1];
	}
	ll get(ll id ,ll L,ll R,ll l,ll r){
		if(L==l && R==r)
			return val[id];
		ll mid=(L+R)/2;
		ll res=0;
		if(l<mid)
			res+=get(id*2,L,mid,l,min(r,mid));
		if(r>mid)
			res+=get(id*2+1,mid,R,max(l,mid),r);
		return res;
	}
}seg[2];
struct fnd{
	set<ll>s[kkk];
	ll get(ll id,ll L,ll R,ll l,ll r){
		if(L==l && R==r)
			return ((s[id].size())?*s[id].rbegin():0);
		ll 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(ll id ,ll L,ll R,ll l,ll r,ll x,bool y){
		if(L==l && R==r){
			if(y)
				s[id].insert(x);
			else
				s[id].erase(x);
			return;
		}
		ll 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(ll i=1;i<n;i++){
		ll 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,1,n+1,1,n);
	seg[1].up(1,1,n+1,1,r);
	fnd.add(1,1,n+1,1,n+1,1,1);
	g[1]=r;
	cout<<ans<<'\n';
	cin>>q;
	while(q--){
		ll ty,x,y,z=1;
		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 t1=seg[0].get(1,1,n+1,st[x],fn[x]+1)-seg[0].get(1,1,n+1,st[x],st[x]+1);
		ll t2=seg[0].get(1,1,n+1,st[z],fn[z]+1)-seg[0].get(1,1,n+1,st[z],st[z]+1);
		ll v1=seg[1].get(1,1,n+1,st[x],fn[x]+1);
		ll v2=seg[1].get(1,1,n+1,st[z],fn[z]+1);
		
		if(bbb){
			cout<<0<<'\n';
		}
		else
			cout<<ans<<'\n';
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:120:11: warning: unused variable 'y' [-Wunused-variable]
  120 |   ll ty,x,y,z=1;
      |           ^
Main.cpp:133:6: warning: unused variable 't1' [-Wunused-variable]
  133 |   ll t1=seg[0].get(1,1,n+1,st[x],fn[x]+1)-seg[0].get(1,1,n+1,st[x],st[x]+1);
      |      ^~
Main.cpp:134:6: warning: unused variable 't2' [-Wunused-variable]
  134 |   ll t2=seg[0].get(1,1,n+1,st[z],fn[z]+1)-seg[0].get(1,1,n+1,st[z],st[z]+1);
      |      ^~
Main.cpp:135:6: warning: unused variable 'v1' [-Wunused-variable]
  135 |   ll v1=seg[1].get(1,1,n+1,st[x],fn[x]+1);
      |      ^~
Main.cpp:136:6: warning: unused variable 'v2' [-Wunused-variable]
  136 |   ll v2=seg[1].get(1,1,n+1,st[z],fn[z]+1);
      |      ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 138464 KB Output is correct
2 Correct 167 ms 136532 KB Output is correct
3 Correct 142 ms 135504 KB Output is correct
4 Correct 170 ms 138324 KB Output is correct
5 Correct 160 ms 133972 KB Output is correct
6 Correct 86 ms 115536 KB Output is correct
7 Correct 86 ms 115540 KB Output is correct
8 Correct 65 ms 113232 KB Output is correct
9 Correct 173 ms 132788 KB Output is correct
10 Correct 188 ms 132948 KB Output is correct
11 Correct 180 ms 132948 KB Output is correct
12 Correct 153 ms 128556 KB Output is correct
13 Correct 160 ms 136784 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 138464 KB Output is correct
2 Correct 167 ms 136532 KB Output is correct
3 Correct 142 ms 135504 KB Output is correct
4 Correct 170 ms 138324 KB Output is correct
5 Correct 160 ms 133972 KB Output is correct
6 Correct 86 ms 115536 KB Output is correct
7 Correct 86 ms 115540 KB Output is correct
8 Correct 65 ms 113232 KB Output is correct
9 Correct 173 ms 132788 KB Output is correct
10 Correct 188 ms 132948 KB Output is correct
11 Correct 180 ms 132948 KB Output is correct
12 Correct 153 ms 128556 KB Output is correct
13 Correct 160 ms 136784 KB Output is correct
14 Incorrect 47 ms 110676 KB Output isn't correct
15 Halted 0 ms 0 KB -