oj.uz

답안 #624021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624021 2022-08-07T06:49:59 Z Arinoor Sumtree (INOI20_sumtree) C++17
10 / 100
 327 ms 98492 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 = 2e5 + 10;
const int maxlg = 19;
const int maxf = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

int n, ans, 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(int a, ll b){
	if(a > b) return 0;
	return mul(fact[b], mul(invfact[a], invfact[b - a]));
}

void update_fact(){
	fact[0] = 1;
	for(int i = 1; i < maxf; i ++)
		fact[i] = mul(fact[i - 1], 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);
	}
	memset(tag, -1, sizeof tag);
	tag[1] = r;
	dfs(1);
	add(fenP, st[1] + 1, 1); add(fenP, ed[1] + 1, -1);
	fill_n(val, maxn, 1);
	ans = val[1] = get_val(1);
	cout << ans << '\n';
	int q; cin >> q;
	while(q--){
		int t, v;
		cin >> t >> v;
		if(t == 1){
			int x; cin >> x;
			tag[v] = x;
			val[v] = get_val(v);
			ans = mul(ans, val[v]);
			int p = find(v);
			ans = mul(ans, inv(val[p]));
			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);
			val[p] = get_val(p);
			ans = mul(ans, val[p]);
			add(fenP, st[v] + 1, 1); add(fenP, ed[v] + 1, -1);
		}
		else{
			ans = mul(ans, inv(val[v]));
			val[v] = 1;
			int p = find(v);
			ans = mul(ans, inv(val[p]));
			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);
			val[p] = get_val(p);
			ans = mul(ans, val[p]);
			add(fenP, st[v] + 1, -1); add(fenP, ed[v] + 1, 1);
			tag[v] = -1;
		}
		cout << ans << '\n';
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 45908 KB Output is correct
2 Correct 163 ms 45764 KB Output is correct
3 Correct 162 ms 45764 KB Output is correct
4 Correct 155 ms 45684 KB Output is correct
5 Correct 138 ms 41880 KB Output is correct
6 Correct 21 ms 14996 KB Output is correct
7 Correct 22 ms 14720 KB Output is correct
8 Correct 20 ms 14788 KB Output is correct
9 Correct 140 ms 38156 KB Output is correct
10 Correct 138 ms 38064 KB Output is correct
11 Correct 135 ms 38164 KB Output is correct
12 Correct 136 ms 36896 KB Output is correct
13 Correct 150 ms 43424 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 45908 KB Output is correct
2 Correct 163 ms 45764 KB Output is correct
3 Correct 162 ms 45764 KB Output is correct
4 Correct 155 ms 45684 KB Output is correct
5 Correct 138 ms 41880 KB Output is correct
6 Correct 21 ms 14996 KB Output is correct
7 Correct 22 ms 14720 KB Output is correct
8 Correct 20 ms 14788 KB Output is correct
9 Correct 140 ms 38156 KB Output is correct
10 Correct 138 ms 38064 KB Output is correct
11 Correct 135 ms 38164 KB Output is correct
12 Correct 136 ms 36896 KB Output is correct
13 Correct 150 ms 43424 KB Output is correct
14 Incorrect 20 ms 14404 KB Output isn't correct
15 Halted 0 ms 0 KB -