oj.uz

Submission #632561

# Submission time Handle Problem Language Result Execution time Memory
632561 2022-08-20T10:39:09 Z codr0 Sumtree (INOI20_sumtree) C++14
30 / 100
 380 ms 148832 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
 
#define F first
#define S second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define err(x) cerr<<#x<<"="<<x<<'\n'
#define lc 2*id
#define rc 2*id+1
#define dmid int mid=(r+l)/2
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define pb push_back
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define bit(i,j) ((j>>i)&1)

using namespace std;
const int md=1e9+7;
const int N=5e5+4;
const int NN=2e5+4;
int n;
vector<int> adj[NN];
int fct[N],inv[N];
int ans,t;
int sz[NN],h[NN],st[NN],en[NN],tme;
int A[NN],B[NN];
struct fenwick{
	int fen[NN];
	void add(int k,int x){
		while(k<NN){
			fen[k]+=x;
			k+=(k&(-k));
		}
	}
	int Get(int k){
		int rt=0;
		while(k>0){
			rt+=fen[k];
			k-=(k&(-k));
		}
		return rt;
	}
	int get(int l,int r){
		return (Get(r)-Get(l-1));
	}
}; fenwick f1,f2;
struct PQ{
	priority_queue<pii> pq1;
	priority_queue<pii> pq2;
	void add(pii x){
		pq1.push(x);
	}
	void erase(pii x){
		pq2.push(x);
	}
	int get(){
		while(!pq2.empty()&&pq1.top()==pq2.top()) pq1.pop(),pq2.pop();
		if(pq1.empty()) return 0;
		return (pq1.top().S);
	}
};
PQ seg[4*NN];
 
	void upd(int id,int l,int r,int v,int x){
		if(st[v]>=r||(en[v]+1)<=l) return;
		if(st[v]<=l&&(en[v]+1)>=r){
			if(x==+1) seg[id].add({h[v],v});
			else seg[id].erase({h[v],v});
			return;
		}
		dmid;
		upd(lc,l,mid,v,x);
		upd(rc,mid,r,v,x);
	}
 
	int get(int id,int l,int r,int v){
		if(st[v]<l||st[v]>=r) return 0;
		int rt=seg[id].get();
		if(l+1==r) return rt;
		dmid;
		int x1=get(lc,l,mid,v);
		int x2=get(rc,mid,r,v);
		if(h[x1]>h[rt]) rt=x1;
		if(h[x2]>h[rt]) rt=x2;
		return rt;
	}
 
	int pw(int a,int b){
		int rt=1;
		while(b){
			if(b&1) rt=1LL*rt*a%md;
			a=1LL*a*a%md;
			b/=2;
		}
		return rt;
	}
 
	int C(int r,int _n){
		if(r<0||r>_n) return 1;
		return (1LL*(1LL*fct[_n]*inv[r]%md)*inv[_n-r]%md);
	}
 
	void dfs(int v,int p){
		h[v]=h[p]+1;
		st[v]=++tme;
		sz[v]=1;
		for(int u:adj[v]) if(u!=p){ dfs(u,v); sz[v]+=sz[u];}
		en[v]=tme;
	}
 
	void add(int v,int w){
		int par=get(1,1,n+1,v);
		upd(1,1,n+1,v,+1);
		f1.add(st[par],-A[par]);
		f2.add(st[par],-B[par]);
		ans=1LL*ans*pw(C(B[par],A[par]+B[par]-1),md-2)%md;
		if(B[par]<0) t--;
		A[v]=sz[v]-f1.get(st[v],en[v]);
		B[v]=w-f2.get(st[v],en[v]);
		A[par]-=A[v];
		B[par]-=B[v];
		f1.add(st[par],A[par]);
		f1.add(st[v],A[v]);
		f2.add(st[par],B[par]);
		f2.add(st[v],B[v]);
		if(B[v]<0) t++;
		if(B[par]<0) t++;
		ans=1LL*ans*C(B[par],A[par]+B[par]-1)%md;
		ans=1LL*ans*C(B[v],A[v]+B[v]-1)%md;
	}

	void rm(int v){
		upd(1,1,n+1,v,-1);
		int par=get(1,1,n+1,v);
		ans=1LL*ans*pw(C(B[par],A[par]+B[par]-1),md-2)%md;
		ans=1LL*ans*pw(C(B[v],A[v]+B[v]-1),md-2)%md;
		f1.add(st[par],-A[par]);
		f2.add(st[par],-B[par]);
		f1.add(st[v],-A[v]);
		f2.add(st[v],-B[v]);
		if(B[v]<0) t--;
		if(B[par]<0) t--;
		f1.add(st[par],A[par]);
		f2.add(st[par],B[par]);
		A[par]+=A[v];
		B[par]+=B[v];
		if(B[par]<0) t--;
		ans=1LL*ans*C(B[par],A[par]+B[par]-1)%md;
	}
 
	void OUT(){
		if(t>0){ cout<<"0\n"; return; }
		cout<<ans<<'\n';
	}
 
	int32_t main(){
	iostream::sync_with_stdio(0); cin.tie(0);
	
	fct[0]=1; FOR(i,1,N-1) fct[i]=1LL*fct[i-1]*i%md;
	inv[N-1]=pw(fct[N-1],md-2); FORR(i,N-2,0) inv[i]=1LL*inv[i+1]*(i+1)%md;
	int k; cin>>n>>k;
	FOR(i,1,n-1){
		int u,v; cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1,1);
	ans=C(k,k+n-1);
	t=0;
	A[1]=n;
	B[1]=k;
	f1.add(st[1],A[1]);
	f2.add(st[1],B[1]);
	upd(1,1,n+1,1,+1);
	OUT();
	int q; cin>>q;
	while(q--){
		int id,v,w;
		cin>>id>>v;
		if(id==1){
			cin>>w;
			add(v,w);
		}else rm(v);
		OUT();
	}
 
	return 0;
	}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 76356 KB Output is correct
2 Correct 133 ms 76288 KB Output is correct
3 Correct 132 ms 76252 KB Output is correct
4 Correct 136 ms 76292 KB Output is correct
5 Correct 126 ms 72352 KB Output is correct
6 Correct 34 ms 59476 KB Output is correct
7 Correct 33 ms 59220 KB Output is correct
8 Correct 33 ms 59348 KB Output is correct
9 Correct 156 ms 68668 KB Output is correct
10 Correct 158 ms 68704 KB Output is correct
11 Correct 135 ms 68716 KB Output is correct
12 Correct 125 ms 68172 KB Output is correct
13 Correct 120 ms 75364 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 59080 KB Output is correct
2 Incorrect 32 ms 59080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 79716 KB Output is correct
2 Correct 186 ms 81740 KB Output is correct
3 Correct 163 ms 80580 KB Output is correct
4 Correct 237 ms 85040 KB Output is correct
5 Correct 380 ms 89288 KB Output is correct
6 Correct 35 ms 59504 KB Output is correct
7 Correct 36 ms 59292 KB Output is correct
8 Correct 35 ms 59448 KB Output is correct
9 Correct 327 ms 77356 KB Output is correct
10 Correct 288 ms 76376 KB Output is correct
11 Correct 269 ms 75816 KB Output is correct
12 Correct 334 ms 76160 KB Output is correct
13 Correct 340 ms 109612 KB Output is correct
14 Correct 357 ms 109632 KB Output is correct
15 Correct 353 ms 109612 KB Output is correct
16 Correct 340 ms 109568 KB Output is correct
17 Correct 334 ms 109572 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 232 ms 148832 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 76356 KB Output is correct
2 Correct 133 ms 76288 KB Output is correct
3 Correct 132 ms 76252 KB Output is correct
4 Correct 136 ms 76292 KB Output is correct
5 Correct 126 ms 72352 KB Output is correct
6 Correct 34 ms 59476 KB Output is correct
7 Correct 33 ms 59220 KB Output is correct
8 Correct 33 ms 59348 KB Output is correct
9 Correct 156 ms 68668 KB Output is correct
10 Correct 158 ms 68704 KB Output is correct
11 Correct 135 ms 68716 KB Output is correct
12 Correct 125 ms 68172 KB Output is correct
13 Correct 120 ms 75364 KB Output is correct
14 Correct 32 ms 59080 KB Output is correct
15 Incorrect 32 ms 59080 KB Output isn't correct
16 Halted 0 ms 0 KB -