oj.uz

Submission #632537

# Submission time Handle Problem Language Result Execution time Memory
632537 2022-08-20T10:09:47 Z codr0 Sumtree (INOI20_sumtree) C++14
10 / 100
 633 ms 352252 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]<=l) return;
		if(x==+1) seg[id].add({h[v],v});
		else seg[id].erase({h[v],v});
		if(l+1==r) 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 161 ms 88800 KB Output is correct
2 Correct 195 ms 88992 KB Output is correct
3 Correct 171 ms 88948 KB Output is correct
4 Correct 169 ms 89012 KB Output is correct
5 Correct 166 ms 84924 KB Output is correct
6 Correct 36 ms 59588 KB Output is correct
7 Correct 42 ms 59424 KB Output is correct
8 Correct 40 ms 59436 KB Output is correct
9 Correct 195 ms 81160 KB Output is correct
10 Correct 158 ms 81156 KB Output is correct
11 Correct 172 ms 81248 KB Output is correct
12 Correct 156 ms 80244 KB Output is correct
13 Correct 142 ms 86720 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 213 ms 170044 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 161 ms 88800 KB Output is correct
2 Correct 195 ms 88992 KB Output is correct
3 Correct 171 ms 88948 KB Output is correct
4 Correct 169 ms 89012 KB Output is correct
5 Correct 166 ms 84924 KB Output is correct
6 Correct 36 ms 59588 KB Output is correct
7 Correct 42 ms 59424 KB Output is correct
8 Correct 40 ms 59436 KB Output is correct
9 Correct 195 ms 81160 KB Output is correct
10 Correct 158 ms 81156 KB Output is correct
11 Correct 172 ms 81248 KB Output is correct
12 Correct 156 ms 80244 KB Output is correct
13 Correct 142 ms 86720 KB Output is correct
14 Runtime error 82 ms 119676 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -