oj.uz

Submission #469899

# Submission time Handle Problem Language Result Execution time Memory
469899 2021-09-02T08:57:49 Z MohammadParsaElahimanesh Sumtree (INOI20_sumtree) C++14
10 / 100
 3000 ms 51248 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 = 2*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<pii> 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(max(x,y) >= Z)while(true);
	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]].upp(mp(H[v],v));
	if(top == X[R[v]].begin())
	{
		v = dad[B[v]];
		return first_up(v);
	}
	else
	{
		--top;
		return (*top).se;
	}
}

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(mp(0,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(mp(H[v],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 210 ms 51140 KB Output is correct
2 Correct 184 ms 51212 KB Output is correct
3 Correct 191 ms 51228 KB Output is correct
4 Correct 203 ms 51248 KB Output is correct
5 Correct 202 ms 47236 KB Output is correct
6 Correct 33 ms 31948 KB Output is correct
7 Correct 32 ms 31824 KB Output is correct
8 Correct 32 ms 31812 KB Output is correct
9 Correct 229 ms 43604 KB Output is correct
10 Correct 232 ms 43556 KB Output is correct
11 Correct 222 ms 43624 KB Output is correct
12 Correct 214 ms 42960 KB Output is correct
13 Correct 166 ms 50028 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 31572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 227 ms 44228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 51140 KB Output is correct
2 Correct 184 ms 51212 KB Output is correct
3 Correct 191 ms 51228 KB Output is correct
4 Correct 203 ms 51248 KB Output is correct
5 Correct 202 ms 47236 KB Output is correct
6 Correct 33 ms 31948 KB Output is correct
7 Correct 32 ms 31824 KB Output is correct
8 Correct 32 ms 31812 KB Output is correct
9 Correct 229 ms 43604 KB Output is correct
10 Correct 232 ms 43556 KB Output is correct
11 Correct 222 ms 43624 KB Output is correct
12 Correct 214 ms 42960 KB Output is correct
13 Correct 166 ms 50028 KB Output is correct
14 Incorrect 32 ms 31572 KB Output isn't correct
15 Halted 0 ms 0 KB -