oj.uz

Submission #624007

# Submission time Handle Problem Language Result Execution time Memory
624007 2022-08-07T06:41:53 Z Arinoor Sumtree (INOI20_sumtree) C++17
10 / 100
 303 ms 97996 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;
int 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, int 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(int *fen, int i, int x){
	for(; i <= n; i += i & -i)
		fen[i] += x;
}

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

int get(int *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]);
	int 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);
			int 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);
			int 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

# Verdict Execution time Memory Grader output
1 Correct 168 ms 48244 KB Output is correct
2 Correct 156 ms 48180 KB Output is correct
3 Correct 155 ms 48228 KB Output is correct
4 Correct 167 ms 48204 KB Output is correct
5 Correct 134 ms 44300 KB Output is correct
6 Correct 20 ms 15060 KB Output is correct
7 Correct 20 ms 14712 KB Output is correct
8 Correct 20 ms 14784 KB Output is correct
9 Correct 141 ms 40580 KB Output is correct
10 Correct 156 ms 40360 KB Output is correct
11 Correct 156 ms 40452 KB Output is correct
12 Correct 143 ms 39264 KB Output is correct
13 Correct 139 ms 45584 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 14452 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 195 ms 97996 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 48244 KB Output is correct
2 Correct 156 ms 48180 KB Output is correct
3 Correct 155 ms 48228 KB Output is correct
4 Correct 167 ms 48204 KB Output is correct
5 Correct 134 ms 44300 KB Output is correct
6 Correct 20 ms 15060 KB Output is correct
7 Correct 20 ms 14712 KB Output is correct
8 Correct 20 ms 14784 KB Output is correct
9 Correct 141 ms 40580 KB Output is correct
10 Correct 156 ms 40360 KB Output is correct
11 Correct 156 ms 40452 KB Output is correct
12 Correct 143 ms 39264 KB Output is correct
13 Correct 139 ms 45584 KB Output is correct
14 Incorrect 22 ms 14452 KB Output isn't correct
15 Halted 0 ms 0 KB -