oj.uz

Submission #469901

# Submission time Handle Problem Language Result Execution time Memory
469901 2021-09-02T09:00:25 Z MohammadParsaElahimanesh Sumtree (INOI20_sumtree) C++14
10 / 100
 215 ms 51516 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(x > y || x < 0 || y >= Z)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 192 ms 51140 KB Output is correct
2 Correct 195 ms 51428 KB Output is correct
3 Correct 215 ms 51124 KB Output is correct
4 Correct 181 ms 51112 KB Output is correct
5 Correct 189 ms 47428 KB Output is correct
6 Correct 33 ms 31956 KB Output is correct
7 Correct 34 ms 31756 KB Output is correct
8 Correct 32 ms 31848 KB Output is correct
9 Correct 208 ms 43716 KB Output is correct
10 Correct 196 ms 43616 KB Output is correct
11 Correct 188 ms 43544 KB Output is correct
12 Correct 197 ms 43104 KB Output is correct
13 Correct 185 ms 50112 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 51140 KB Output is correct
2 Correct 195 ms 51428 KB Output is correct
3 Correct 215 ms 51124 KB Output is correct
4 Correct 181 ms 51112 KB Output is correct
5 Correct 189 ms 47428 KB Output is correct
6 Correct 33 ms 31956 KB Output is correct
7 Correct 34 ms 31756 KB Output is correct
8 Correct 32 ms 31848 KB Output is correct
9 Correct 208 ms 43716 KB Output is correct
10 Correct 196 ms 43616 KB Output is correct
11 Correct 188 ms 43544 KB Output is correct
12 Correct 197 ms 43104 KB Output is correct
13 Correct 185 ms 50112 KB Output is correct
14 Incorrect 32 ms 31628 KB Output isn't correct
15 Halted 0 ms 0 KB -