oj.uz

Submission #947695

# Submission time Handle Problem Language Result Execution time Memory
947695 2024-03-16T20:24:26 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 258 ms 137712 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){
		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(int id,int L,int R,int l,int x){
		if(L+1==R){
			val[id]=x;
			return;
		}
		int 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(int id ,int L,int R,int l,int r){
		if(L==l && R==r)
			return val[id];
		int 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<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,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--){
		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);
		}
		
		int t1=seg[0].get(1,1,n+1,st[x],fn[x]+1);
		
			cout<<ans<<'\n';
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:120:12: warning: unused variable 'y' [-Wunused-variable]
  120 |   int ty,x,y,z;
      |            ^
Main.cpp:120:14: warning: variable 'z' set but not used [-Wunused-but-set-variable]
  120 |   int ty,x,y,z;
      |              ^
Main.cpp:133:7: warning: unused variable 't1' [-Wunused-variable]
  133 |   int t1=seg[0].get(1,1,n+1,st[x],fn[x]+1);
      |       ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 134996 KB Output is correct
2 Correct 127 ms 132688 KB Output is correct
3 Correct 139 ms 131724 KB Output is correct
4 Correct 136 ms 134224 KB Output is correct
5 Correct 133 ms 131132 KB Output is correct
6 Correct 58 ms 117756 KB Output is correct
7 Correct 60 ms 117668 KB Output is correct
8 Correct 42 ms 115428 KB Output is correct
9 Correct 139 ms 128852 KB Output is correct
10 Correct 144 ms 129108 KB Output is correct
11 Correct 141 ms 129316 KB Output is correct
12 Correct 142 ms 125148 KB Output is correct
13 Correct 142 ms 133460 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 134996 KB Output is correct
2 Correct 127 ms 132688 KB Output is correct
3 Correct 139 ms 131724 KB Output is correct
4 Correct 136 ms 134224 KB Output is correct
5 Correct 133 ms 131132 KB Output is correct
6 Correct 58 ms 117756 KB Output is correct
7 Correct 60 ms 117668 KB Output is correct
8 Correct 42 ms 115428 KB Output is correct
9 Correct 139 ms 128852 KB Output is correct
10 Correct 144 ms 129108 KB Output is correct
11 Correct 141 ms 129316 KB Output is correct
12 Correct 142 ms 125148 KB Output is correct
13 Correct 142 ms 133460 KB Output is correct
14 Incorrect 23 ms 113500 KB Output isn't correct
15 Halted 0 ms 0 KB -