oj.uz

Submission #632543

# Submission time Handle Problem Language Result Execution time Memory
632543 2022-08-20T10:21:01 Z codr0 Sumtree (INOI20_sumtree) C++14
10 / 100
 3000 ms 583312 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});
		}
		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 164 ms 88888 KB Output is correct
2 Correct 159 ms 88800 KB Output is correct
3 Correct 182 ms 88868 KB Output is correct
4 Correct 167 ms 88828 KB Output is correct
5 Correct 168 ms 84860 KB Output is correct
6 Correct 40 ms 59660 KB Output is correct
7 Correct 38 ms 59340 KB Output is correct
8 Correct 34 ms 59476 KB Output is correct
9 Correct 157 ms 81176 KB Output is correct
10 Correct 169 ms 81164 KB Output is correct
11 Correct 175 ms 81244 KB Output is correct
12 Correct 162 ms 80032 KB Output is correct
13 Correct 149 ms 86604 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3096 ms 583312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 235 ms 170060 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 164 ms 88888 KB Output is correct
2 Correct 159 ms 88800 KB Output is correct
3 Correct 182 ms 88868 KB Output is correct
4 Correct 167 ms 88828 KB Output is correct
5 Correct 168 ms 84860 KB Output is correct
6 Correct 40 ms 59660 KB Output is correct
7 Correct 38 ms 59340 KB Output is correct
8 Correct 34 ms 59476 KB Output is correct
9 Correct 157 ms 81176 KB Output is correct
10 Correct 169 ms 81164 KB Output is correct
11 Correct 175 ms 81244 KB Output is correct
12 Correct 162 ms 80032 KB Output is correct
13 Correct 149 ms 86604 KB Output is correct
14 Runtime error 79 ms 119628 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -