oj.uz

답안 #469887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469887 2021-09-02T08:45:04 Z MohammadParsaElahimanesh Sumtree (INOI20_sumtree) C++14
10 / 100
 214 ms 87500 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<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

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 43340 KB Output is correct
2 Correct 183 ms 43332 KB Output is correct
3 Correct 185 ms 43380 KB Output is correct
4 Correct 177 ms 43364 KB Output is correct
5 Correct 204 ms 39428 KB Output is correct
6 Correct 27 ms 24204 KB Output is correct
7 Correct 22 ms 23912 KB Output is correct
8 Correct 20 ms 24044 KB Output is correct
9 Correct 191 ms 35876 KB Output is correct
10 Correct 192 ms 35640 KB Output is correct
11 Correct 193 ms 35780 KB Output is correct
12 Correct 167 ms 35136 KB Output is correct
13 Correct 165 ms 42232 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 23788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 214 ms 87500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 185 ms 36372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 43340 KB Output is correct
2 Correct 183 ms 43332 KB Output is correct
3 Correct 185 ms 43380 KB Output is correct
4 Correct 177 ms 43364 KB Output is correct
5 Correct 204 ms 39428 KB Output is correct
6 Correct 27 ms 24204 KB Output is correct
7 Correct 22 ms 23912 KB Output is correct
8 Correct 20 ms 24044 KB Output is correct
9 Correct 191 ms 35876 KB Output is correct
10 Correct 192 ms 35640 KB Output is correct
11 Correct 193 ms 35780 KB Output is correct
12 Correct 167 ms 35136 KB Output is correct
13 Correct 165 ms 42232 KB Output is correct
14 Incorrect 20 ms 23788 KB Output isn't correct
15 Halted 0 ms 0 KB -