oj.uz

Submission #469903

# Submission time Handle Problem Language Result Execution time Memory
469903 2021-09-02T09:02:37 Z MohammadParsaElahimanesh Sumtree (INOI20_sumtree) C++14
10 / 100
 282 ms 135360 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 = 4*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)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 224 ms 66876 KB Output is correct
2 Correct 219 ms 66884 KB Output is correct
3 Correct 217 ms 66884 KB Output is correct
4 Correct 240 ms 66884 KB Output is correct
5 Correct 183 ms 62916 KB Output is correct
6 Correct 56 ms 47708 KB Output is correct
7 Correct 57 ms 47424 KB Output is correct
8 Correct 55 ms 47428 KB Output is correct
9 Correct 210 ms 59220 KB Output is correct
10 Correct 202 ms 59204 KB Output is correct
11 Correct 212 ms 59264 KB Output is correct
12 Correct 197 ms 58620 KB Output is correct
13 Correct 180 ms 65748 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 66876 KB Output is correct
2 Correct 219 ms 66884 KB Output is correct
3 Correct 217 ms 66884 KB Output is correct
4 Correct 240 ms 66884 KB Output is correct
5 Correct 183 ms 62916 KB Output is correct
6 Correct 56 ms 47708 KB Output is correct
7 Correct 57 ms 47424 KB Output is correct
8 Correct 55 ms 47428 KB Output is correct
9 Correct 210 ms 59220 KB Output is correct
10 Correct 202 ms 59204 KB Output is correct
11 Correct 212 ms 59264 KB Output is correct
12 Correct 197 ms 58620 KB Output is correct
13 Correct 180 ms 65748 KB Output is correct
14 Incorrect 52 ms 47284 KB Output isn't correct
15 Halted 0 ms 0 KB -