oj.uz

Submission #632569

# Submission time Handle Problem Language Result Execution time Memory
632569 2022-08-20T10:48:10 Z codr0 Sumtree (INOI20_sumtree) C++14
30 / 100
 502 ms 109716 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--;
		A[par]+=A[v];
		B[par]+=B[v];
		f1.add(st[par],A[par]);
		f2.add(st[par],B[par]);
		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 179 ms 76296 KB Output is correct
2 Correct 164 ms 76368 KB Output is correct
3 Correct 129 ms 76252 KB Output is correct
4 Correct 139 ms 76344 KB Output is correct
5 Correct 135 ms 72400 KB Output is correct
6 Correct 34 ms 59468 KB Output is correct
7 Correct 40 ms 59172 KB Output is correct
8 Correct 34 ms 59176 KB Output is correct
9 Correct 137 ms 68668 KB Output is correct
10 Correct 155 ms 68740 KB Output is correct
11 Correct 166 ms 68724 KB Output is correct
12 Correct 150 ms 68172 KB Output is correct
13 Correct 129 ms 75420 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 59084 KB Output is correct
2 Correct 33 ms 59028 KB Output is correct
3 Correct 36 ms 59092 KB Output is correct
4 Correct 34 ms 59100 KB Output is correct
5 Correct 36 ms 59148 KB Output is correct
6 Correct 36 ms 59364 KB Output is correct
7 Correct 41 ms 59332 KB Output is correct
8 Correct 35 ms 59376 KB Output is correct
9 Correct 38 ms 59412 KB Output is correct
10 Correct 41 ms 59552 KB Output is correct
11 Correct 41 ms 59724 KB Output is correct
12 Correct 36 ms 59340 KB Output is correct
13 Correct 39 ms 59648 KB Output is correct
14 Correct 39 ms 59552 KB Output is correct
15 Correct 39 ms 59792 KB Output is correct
16 Correct 42 ms 59516 KB Output is correct
17 Correct 43 ms 59596 KB Output is correct
18 Correct 39 ms 59368 KB Output is correct
19 Correct 38 ms 59504 KB Output is correct
20 Incorrect 37 ms 59356 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 79692 KB Output is correct
2 Correct 196 ms 81724 KB Output is correct
3 Correct 152 ms 80588 KB Output is correct
4 Correct 239 ms 84960 KB Output is correct
5 Correct 398 ms 89304 KB Output is correct
6 Correct 35 ms 59536 KB Output is correct
7 Correct 35 ms 59324 KB Output is correct
8 Correct 36 ms 59348 KB Output is correct
9 Correct 326 ms 77376 KB Output is correct
10 Correct 283 ms 76376 KB Output is correct
11 Correct 275 ms 75812 KB Output is correct
12 Correct 310 ms 76108 KB Output is correct
13 Correct 330 ms 109716 KB Output is correct
14 Correct 347 ms 109576 KB Output is correct
15 Correct 364 ms 109588 KB Output is correct
16 Correct 346 ms 109532 KB Output is correct
17 Correct 347 ms 109572 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 82892 KB Output is correct
2 Correct 478 ms 85632 KB Output is correct
3 Correct 502 ms 85708 KB Output is correct
4 Correct 493 ms 85856 KB Output is correct
5 Correct 489 ms 84940 KB Output is correct
6 Correct 491 ms 85600 KB Output is correct
7 Correct 394 ms 75980 KB Output is correct
8 Correct 429 ms 76096 KB Output is correct
9 Correct 487 ms 85736 KB Output is correct
10 Correct 481 ms 85796 KB Output is correct
11 Correct 476 ms 86084 KB Output is correct
12 Correct 370 ms 76236 KB Output is correct
13 Incorrect 311 ms 72672 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 76296 KB Output is correct
2 Correct 164 ms 76368 KB Output is correct
3 Correct 129 ms 76252 KB Output is correct
4 Correct 139 ms 76344 KB Output is correct
5 Correct 135 ms 72400 KB Output is correct
6 Correct 34 ms 59468 KB Output is correct
7 Correct 40 ms 59172 KB Output is correct
8 Correct 34 ms 59176 KB Output is correct
9 Correct 137 ms 68668 KB Output is correct
10 Correct 155 ms 68740 KB Output is correct
11 Correct 166 ms 68724 KB Output is correct
12 Correct 150 ms 68172 KB Output is correct
13 Correct 129 ms 75420 KB Output is correct
14 Correct 33 ms 59084 KB Output is correct
15 Correct 33 ms 59028 KB Output is correct
16 Correct 36 ms 59092 KB Output is correct
17 Correct 34 ms 59100 KB Output is correct
18 Correct 36 ms 59148 KB Output is correct
19 Correct 36 ms 59364 KB Output is correct
20 Correct 41 ms 59332 KB Output is correct
21 Correct 35 ms 59376 KB Output is correct
22 Correct 38 ms 59412 KB Output is correct
23 Correct 41 ms 59552 KB Output is correct
24 Correct 41 ms 59724 KB Output is correct
25 Correct 36 ms 59340 KB Output is correct
26 Correct 39 ms 59648 KB Output is correct
27 Correct 39 ms 59552 KB Output is correct
28 Correct 39 ms 59792 KB Output is correct
29 Correct 42 ms 59516 KB Output is correct
30 Correct 43 ms 59596 KB Output is correct
31 Correct 39 ms 59368 KB Output is correct
32 Correct 38 ms 59504 KB Output is correct
33 Incorrect 37 ms 59356 KB Output isn't correct
34 Halted 0 ms 0 KB -