oj.uz

Submission #632551

# Submission time Handle Problem Language Result Execution time Memory
632551 2022-08-20T10:27:53 Z codr0 Sumtree (INOI20_sumtree) C++14
30 / 100
 391 ms 144608 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 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;
		assert(id==1);
		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 147 ms 76464 KB Output is correct
2 Correct 157 ms 76424 KB Output is correct
3 Correct 131 ms 76436 KB Output is correct
4 Correct 133 ms 76512 KB Output is correct
5 Correct 127 ms 72408 KB Output is correct
6 Correct 36 ms 59440 KB Output is correct
7 Correct 34 ms 59212 KB Output is correct
8 Correct 35 ms 59272 KB Output is correct
9 Correct 131 ms 68804 KB Output is correct
10 Correct 131 ms 68812 KB Output is correct
11 Correct 142 ms 68788 KB Output is correct
12 Correct 144 ms 68368 KB Output is correct
13 Correct 122 ms 75472 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 77 ms 119704 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 79912 KB Output is correct
2 Correct 220 ms 84436 KB Output is correct
3 Correct 173 ms 83056 KB Output is correct
4 Correct 250 ms 87920 KB Output is correct
5 Correct 391 ms 93148 KB Output is correct
6 Correct 36 ms 59620 KB Output is correct
7 Correct 36 ms 59288 KB Output is correct
8 Correct 38 ms 59468 KB Output is correct
9 Correct 338 ms 80844 KB Output is correct
10 Correct 294 ms 79484 KB Output is correct
11 Correct 276 ms 78984 KB Output is correct
12 Correct 306 ms 79832 KB Output is correct
13 Correct 349 ms 115040 KB Output is correct
14 Correct 339 ms 115108 KB Output is correct
15 Correct 357 ms 115088 KB Output is correct
16 Correct 335 ms 114988 KB Output is correct
17 Correct 345 ms 114936 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 237 ms 144608 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 76464 KB Output is correct
2 Correct 157 ms 76424 KB Output is correct
3 Correct 131 ms 76436 KB Output is correct
4 Correct 133 ms 76512 KB Output is correct
5 Correct 127 ms 72408 KB Output is correct
6 Correct 36 ms 59440 KB Output is correct
7 Correct 34 ms 59212 KB Output is correct
8 Correct 35 ms 59272 KB Output is correct
9 Correct 131 ms 68804 KB Output is correct
10 Correct 131 ms 68812 KB Output is correct
11 Correct 142 ms 68788 KB Output is correct
12 Correct 144 ms 68368 KB Output is correct
13 Correct 122 ms 75472 KB Output is correct
14 Runtime error 77 ms 119704 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -