oj.uz

답안 #624128

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624128 2022-08-07T10:02:15 Z Arinoor Sumtree (INOI20_sumtree) C++17
10 / 100
 523 ms 71772 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e6 + 10;
const int maxlg = 19;
const int maxf = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int n, fact[maxf], invfact[maxf];
int val[maxn], tag[maxn];
int par[maxn][maxlg], sz[maxn], st[maxn], ed[maxn], tme = 1;
ll fenC[maxn], fenS[maxn], fenP[maxn];
vector<int> G[maxn];

int add(int a, int b){
	int c = a + b;
	if(c >= mod) c -= mod;
	if(c < 0) c += mod;
	return c;
}

int mul(int a, int b){
	return 1ll * a * b % mod;
}

int pwr(int a, int b){
	int res = 1;
	for(; b; b >>= 1, a = mul(a, a)) if(b & 1) res = mul(res, a);
	return res;
}

int inv(int a){
	return pwr(a, mod - 2);
}

int C(ll a, ll b){
	if(a > b)
		return 0;
	if(a < 0 or a >= maxf or b >= maxf or b < 0){
		return 0;
	}
	return mul(fact[b], mul(invfact[a], invfact[b - a]));
}

void update_fact(){
	fact[0] = invfact[0] = 1;
	for(int i = 1; i < maxf; i ++){
		fact[i] = mul(fact[i - 1], i);
		invfact[i] = inv(fact[i]);
	}
	/*
	invfact[maxf - 1] = inv(fact[maxf - 1]);
	for(int i = maxf - 2; ~i; i --)
		invfact[i] = mul(invfact[i + 1], i + 1);
		*/
}

void add(ll *fen, int i, ll x){
	for(; i <= n; i += i & -i)
		fen[i] += x;
}

ll get(ll *fen, int i){
	ll res = 0;
	for(; i; i -= i & -i)
		res += fen[i];
	return res;
}

ll get(ll *fen, int l, int r){
	return get(fen, r) - get(fen, l - 1);
}

void dfs(int v, int p = 0){
	par[v][0] = p;
	for(int i = 1; i < maxlg and par[v][i - 1]; i ++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	st[v] = tme;
	sz[v] = 1;
	for(int u : G[v]){
		if(u ^ p){
			tme ++;
			dfs(u, v);
			sz[v] += sz[u];
		}
	}
	ed[v] = tme;
}

int get_val(int v){
	int cnt = sz[v] - get(fenC, st[v] + 1, ed[v]);
	ll sum = tag[v] - get(fenS, st[v] + 1, ed[v]);
	return C(cnt - 1, cnt + sum - 1);
}

int find(int v){
	int x = get(fenP, st[v]);
	for(int i = maxlg - 1; ~i; i --){
		int u = par[v][i];
		if(!u) continue;
		if(get(fenP, st[u]) == x)
			v = u;
	}
	return par[v][0];
}

int main(){
	ios;
	update_fact();
	int r;
	cin >> n >> r;
	for(int i = 0; i < n - 1; i ++){
		int u, v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1);
	memset(tag, -1, sizeof tag);
	tag[1] = r;
	add(fenP, st[1] + 1, 1); add(fenP, ed[1] + 1, -1);
	for(int i = 2; i <= n; i ++)
		val[i] = 1;
	val[1] = get_val(1);
	int ans = val[1];
	cout << ans << '\n';
	int q; cin >> q;
	int Cnt = 0;
	while(q--){
		int t, v;
		cin >> t >> v;
		if(t == 1){
			int x; cin >> x;
			tag[v] = x;
			val[v] = get_val(v);
			if(val[v])
				ans = mul(ans, val[v]);
			else
				Cnt ++;
			int cnt = sz[v] - get(fenC, st[v] + 1, ed[v]);
			add(fenC, st[v], cnt);
			ll sum = tag[v] - get(fenS, st[v] + 1, ed[v]);
			add(fenS, st[v], sum);
			add(fenP, st[v] + 1, 1); add(fenP, ed[v] + 1, -1);
			int p = find(v);
			if(inv(val[p]))
				ans = mul(ans, inv(val[p]));
			else
				Cnt --;
			val[p] = get_val(p);
			if(val[p])
				ans = mul(ans, val[p]);
			else
				Cnt ++;
		}
		else{
			if(inv(val[v]))
				ans = mul(ans, inv(val[v]));
			else
				Cnt --;
			val[v] = 1;
			int cnt = sz[v] - get(fenC, st[v] + 1, ed[v]);
			add(fenC, st[v], -cnt);
			ll sum = tag[v] - get(fenS, st[v] + 1, ed[v]);
			add(fenS, st[v], -sum);
			add(fenP, st[v] + 1, -1); add(fenP, ed[v] + 1, 1);
			int p = find(v);
			if(inv(val[p]))
				ans = mul(ans, inv(val[p]));
			else
				Cnt --;
			val[p] = get_val(p);
			if(val[p])
				ans = mul(ans, val[p]);
			else
				Cnt ++;
			tag[v] = -1;
		}
		if(Cnt)
			cout << "0\n";
		else
			cout << ans << '\n';
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 310 ms 67672 KB Output is correct
2 Correct 307 ms 67744 KB Output is correct
3 Correct 302 ms 67660 KB Output is correct
4 Correct 315 ms 67732 KB Output is correct
5 Correct 287 ms 63796 KB Output is correct
6 Correct 176 ms 36188 KB Output is correct
7 Correct 180 ms 35916 KB Output is correct
8 Correct 176 ms 35968 KB Output is correct
9 Correct 296 ms 60088 KB Output is correct
10 Correct 291 ms 59976 KB Output is correct
11 Correct 278 ms 60032 KB Output is correct
12 Correct 287 ms 58788 KB Output is correct
13 Correct 292 ms 65428 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 310 ms 67672 KB Output is correct
2 Correct 307 ms 67744 KB Output is correct
3 Correct 302 ms 67660 KB Output is correct
4 Correct 315 ms 67732 KB Output is correct
5 Correct 287 ms 63796 KB Output is correct
6 Correct 176 ms 36188 KB Output is correct
7 Correct 180 ms 35916 KB Output is correct
8 Correct 176 ms 35968 KB Output is correct
9 Correct 296 ms 60088 KB Output is correct
10 Correct 291 ms 59976 KB Output is correct
11 Correct 278 ms 60032 KB Output is correct
12 Correct 287 ms 58788 KB Output is correct
13 Correct 292 ms 65428 KB Output is correct
14 Incorrect 172 ms 35580 KB Output isn't correct
15 Halted 0 ms 0 KB -