oj.uz

Submission #469883

# Submission time Handle Problem Language Result Execution time Memory
469883 2021-09-02T08:31:25 Z MohammadParsaElahimanesh Sumtree (INOI20_sumtree) C++14
10 / 100
 3000 ms 87520 KB 
/// In the name of Allah

#include <bits/stdc++.h>

using namespace std;

#define Fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define RFOR(i,a) for(int i = a-1; i >= 0; i--)
#define FOR(i,a) for(int i = 0; i < a; i++)
#define se second
#define fi first
#define sz(x) (int)x.size()
#define upp upper_bound
#define low lower_bound
#define pub push_back
#define all(x) x.begin(),x.end()
#define mp make_pair

typedef double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const ll mod = 1'000'000'007;
const int N = 200'000 + 5;
const int Z = 500'000 + 5;
ll F[Z], _F[Z], ans;
int n, r, q, H[N], S[N], dad[N], st[N], en[N], R[N], B[N], tag[N], timer = 1, p = 0, cnt = 0;
set<int> X[N];
vector<int> G[N];

inline ll Pow(ll a, int b)
{
	ll res = 1LL;
	while(b)
	{
		if(b&1)res = res*a%mod;
		b >>= 1;
		a = a*a%mod;
	}
	return res;
}

inline ll inv(int x){return Pow(x,mod-2);}

inline ll C(int x, int y)
{
	if(x > y || x < 0)return 0;
	return F[y]*_F[x]%mod*_F[y-x]%mod;
}

struct fen
{
	int G[N];
	fen(){memset(G,0,sizeof(G));}
	inline void inc(int p, int x)
	{
		while(p < N)
		{
			G[p] += x;
			p += p&-p;
		}
	}
	inline int get(int p)
	{
		int s = 0;
		while(p)
		{
			s += G[p];
			p -= p&-p;
		}
		return s;
	}
}tags, Free;


int dfs_s(int v, int d, int h)
{
	st[v] = timer++;
	H[v] = h;
	dad[v] = d;
	S[v] = 1;
	for(auto u: G[v])if(u != d)S[v] += dfs_s(u,v,h+1);
	en[v] = timer;
	return S[v];
}

void dfs_hld(int v, int top, int nam)
{
	R[v] = nam;
	B[v] = top;
	pii MAX = mp(-1,-2);
	for(auto u: G[v])if(u != dad[v])MAX = max(MAX,mp(S[u],u));
	for(auto u: G[v])if(u != dad[v])
	{
		if(MAX.se == u)dfs_hld(u,top,nam);
		else dfs_hld(u,u,p++);
	}
}

inline int first_up(int v)
{
	auto top = X[R[v]].low(H[v]);
	if(top == X[R[v]].begin())
	{
		v = dad[B[v]];
		return first_up(v);
	}
	else
	{
		top--;
		return *top;
	}
}

inline void upd(int v, int tg, int fs)
{
	int nfs = S[v]-Free.get(en[v]-1)+Free.get(st[v]);
	int ntg = tag[v]-tags.get(en[v]-1)+tags.get(st[v]);
	
	if(C(ntg,nfs+ntg-1) == 0)cnt++;
	else ans = ans*C(ntg,nfs+ntg-1)%mod;
	
	nfs += fs;
	ntg += tg;
	
	if(C(ntg,nfs+ntg-1) == 0)cnt--;
	else ans = ans*inv(C(ntg,nfs+ntg-1))%mod;
}

int main()
{
	Fast
	
	F[0] = 1;
	for(ll i = 1; i < Z; i++)F[i] = i*F[i-1]%mod;
	_F[Z-1] = inv(F[Z-1]);
	for(ll i = Z-2; i >= 0; i--)_F[i] = (i+1LL)*_F[i+1]%mod;
	
	cin >> n >> r;
	
	int u, v, x, t;
	FOR(i,n-1)
	{
		cin >> u >> v;
		u--; v--;
		G[u].pub(v); G[v].pub(u);
	}
	dfs_s(0,0,0);
	dfs_hld(0,0,p++);
	tag[0] = r;
	X[R[0]].insert(0);
	tags.inc(st[0],r);
	Free.inc(st[0],n);
	ans = C(r,n+r-1);
	cout << ans << '\n';
	
	cin >> q;
	
	FOR(i,q)
	{
		cin >> t;
		if(t == 1)
		{
			cin >> v >> x;
			v--;
			tag[v] = x;
			u = first_up(v);
			
			int fs = S[v]-Free.get(en[v]-1)+Free.get(st[v]);
			int tg = x-tags.get(en[v]-1)+tags.get(st[v]);
			Free.inc(st[v],fs);
			tags.inc(st[v],tg);
			
			if(C(tg,fs+tg-1) == 0)cnt++;
			else ans = (ans*C(tg,fs+tg-1))%mod;
			upd(u,tg,fs);
			X[R[v]].insert(H[v]);
		}
		else
		{
			cin >> v;
			v--;
			return 0;
		}
		
		cout << (cnt?0:ans) << '\n';
	}
	
	return 0;
}

// thank god

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 43332 KB Output is correct
2 Correct 187 ms 43400 KB Output is correct
3 Correct 182 ms 43352 KB Output is correct
4 Correct 183 ms 43396 KB Output is correct
5 Correct 184 ms 39424 KB Output is correct
6 Correct 22 ms 24140 KB Output is correct
7 Correct 22 ms 23960 KB Output is correct
8 Correct 21 ms 23992 KB Output is correct
9 Correct 202 ms 35896 KB Output is correct
10 Correct 205 ms 35792 KB Output is correct
11 Correct 189 ms 35724 KB Output is correct
12 Correct 185 ms 35140 KB Output is correct
13 Correct 160 ms 42112 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 43332 KB Output is correct
2 Correct 187 ms 43400 KB Output is correct
3 Correct 182 ms 43352 KB Output is correct
4 Correct 183 ms 43396 KB Output is correct
5 Correct 184 ms 39424 KB Output is correct
6 Correct 22 ms 24140 KB Output is correct
7 Correct 22 ms 23960 KB Output is correct
8 Correct 21 ms 23992 KB Output is correct
9 Correct 202 ms 35896 KB Output is correct
10 Correct 205 ms 35792 KB Output is correct
11 Correct 189 ms 35724 KB Output is correct
12 Correct 185 ms 35140 KB Output is correct
13 Correct 160 ms 42112 KB Output is correct
14 Execution timed out 3069 ms 23756 KB Time limit exceeded
15 Halted 0 ms 0 KB -