oj.uz

Submission #947694

# Submission time Handle Problem Language Result Execution time Memory
947694 2024-03-16T20:23:37 Z PM1 Sumtree (INOI20_sumtree) C++17
10 / 100
 238 ms 135020 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];
			
		}
		else{
			cin>>x;
	
		}
		
		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: unused variable 'z' [-Wunused-variable]
  120 |   int ty,x,y,z;
      |              ^
Main.cpp:131:7: warning: unused variable 't1' [-Wunused-variable]
  131 |   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 167 ms 135020 KB Output is correct
2 Correct 127 ms 132692 KB Output is correct
3 Correct 133 ms 131668 KB Output is correct
4 Correct 138 ms 134208 KB Output is correct
5 Correct 143 ms 131464 KB Output is correct
6 Correct 58 ms 117752 KB Output is correct
7 Correct 58 ms 117324 KB Output is correct
8 Correct 42 ms 115268 KB Output is correct
9 Correct 143 ms 129092 KB Output is correct
10 Correct 150 ms 129360 KB Output is correct
11 Correct 142 ms 129104 KB Output is correct
12 Correct 117 ms 125264 KB Output is correct
13 Correct 156 ms 133860 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 135020 KB Output is correct
2 Correct 127 ms 132692 KB Output is correct
3 Correct 133 ms 131668 KB Output is correct
4 Correct 138 ms 134208 KB Output is correct
5 Correct 143 ms 131464 KB Output is correct
6 Correct 58 ms 117752 KB Output is correct
7 Correct 58 ms 117324 KB Output is correct
8 Correct 42 ms 115268 KB Output is correct
9 Correct 143 ms 129092 KB Output is correct
10 Correct 150 ms 129360 KB Output is correct
11 Correct 142 ms 129104 KB Output is correct
12 Correct 117 ms 125264 KB Output is correct
13 Correct 156 ms 133860 KB Output is correct
14 Incorrect 25 ms 113184 KB Output isn't correct
15 Halted 0 ms 0 KB -