oj.uz

Submission #624124

# Submission time Handle Problem Language Result Execution time Memory
624124 2022-08-07T09:56:06 Z Arinoor Sumtree (INOI20_sumtree) C++17
10 / 100
 339 ms 68588 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(b < 0 or b >= maxf){
		cout << "-2\n";
		exit(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

# Verdict Execution time Memory Grader output
1 Correct 305 ms 67756 KB Output is correct
2 Correct 299 ms 67684 KB Output is correct
3 Correct 309 ms 67652 KB Output is correct
4 Correct 313 ms 67860 KB Output is correct
5 Correct 291 ms 63752 KB Output is correct
6 Correct 171 ms 36104 KB Output is correct
7 Correct 182 ms 35968 KB Output is correct
8 Correct 178 ms 35988 KB Output is correct
9 Correct 290 ms 60148 KB Output is correct
10 Correct 339 ms 60036 KB Output is correct
11 Correct 302 ms 60116 KB Output is correct
12 Correct 307 ms 58832 KB Output is correct
13 Correct 307 ms 65260 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 67756 KB Output is correct
2 Correct 299 ms 67684 KB Output is correct
3 Correct 309 ms 67652 KB Output is correct
4 Correct 313 ms 67860 KB Output is correct
5 Correct 291 ms 63752 KB Output is correct
6 Correct 171 ms 36104 KB Output is correct
7 Correct 182 ms 35968 KB Output is correct
8 Correct 178 ms 35988 KB Output is correct
9 Correct 290 ms 60148 KB Output is correct
10 Correct 339 ms 60036 KB Output is correct
11 Correct 302 ms 60116 KB Output is correct
12 Correct 307 ms 58832 KB Output is correct
13 Correct 307 ms 65260 KB Output is correct
14 Incorrect 176 ms 35628 KB Output isn't correct
15 Halted 0 ms 0 KB -