oj.uz

Submission #633722

# Submission time Handle Problem Language Result Execution time Memory
633722 2022-08-23T07:06:52 Z NothingXD Sumtree (INOI20_sumtree) C++17
100 / 100
 808 ms 55180 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef __uint128_t L;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;

int add(int x, int y){
	int res = x + y;
	if (res >= mod) return res - mod;
	if (res < 0) return res + mod;
	return res;
}

int mul(int x, int y){
	return 1ll * x * y % mod;
}

int pwr(int a, int b){
	int res = 1;
	for (; b; b >>= 1, a = 1LL * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
	return res;
}

int r, n, q, cnt, sz[maxn], seg[maxn << 2], st[maxn], en[maxn], ver[maxn], fact[maxn], invfact[maxn], ans, tme;
ll a[maxn], f[maxn], F[maxn];
vector<int> g[maxn];
bool bad[maxn];

int C(int n, int k){
	return mul(fact[n], mul(invfact[k], invfact[n-k]));
}

void dfs(int v, int p = -1){
	st[v] = ++tme;
	ver[tme] = v;
	sz[v] = 1;
	for (auto u: g[v]){
		if (u != p){
			dfs(u, v);
			sz[v] += sz[u];
		}
	}
	en[v] = tme;
}

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

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

ll get(ll *f, int l, int r){
	if (r < l) return 0;
	return get(f, r) - get(f, l-1);
}

void change(int v, int l, int r, int idx, int val){
	if (idx < l || r <= idx) return;
	if (l + 1 == r){
		seg[v] = val;
		return;
	}
	int mid = (l + r) >> 1;
	change(v << 1, l, mid, idx, val);
	change(v << 1 | 1, mid, r, idx, val);
	seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
}

int find(int v, int l, int r, int ql, int qr, int val){
	if (qr <= l || r <= ql) return -1;
	if (ql <= l && r <= qr && seg[v] < val) return -1;
	if (l + 1 == r) return ver[l];
	int mid = (l + r) >> 1;
	int res = find(v << 1 | 1, mid, r, ql, qr, val);
	if (res == -1) res = find(v << 1, l, mid, ql, qr, val);
	return res;
}

void add(int idx){
	ll X = sz[idx] - get(f, st[idx] + 1, en[idx]);
	ll Y = a[idx] - get(F, st[idx] + 1, en[idx]);
	add(f, st[idx], X);
	add(F, st[idx], Y);
	change(1, 1, n+1, st[idx], en[idx]);
	if (Y < 0){
		bad[idx] = true;
		cnt++;
		return;
	}
	ans = mul(ans, C(X + Y - 1, X - 1));
}

void remove(int idx){
	ll X = get(f, st[idx], st[idx]);
	ll Y = get(F, st[idx], st[idx]);
	if (bad[idx]){
		bad[idx] = false;
		cnt--;
	}
	else{
		ans = mul(ans, pwr(C(X + Y - 1, X - 1), mod - 2));
	}
	add(f, st[idx], -X);
	add(F, st[idx], -Y);
	change(1, 1, n+1, st[idx], 0);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	fact[0] = invfact[0] = 1;
	for (int i = 1; i < maxn; i++){
		fact[i] = 1ll * fact[i-1] * i % mod;
		invfact[i] = pwr(fact[i], mod-2);
	}

	cin >> n >> r;

	for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(1);

	a[1] = r;
	change(1, 1, n+1, 1, n);
	add(f, 1, n);
	add(F, 1, r);
	ans = C(r + n - 1, n-1);
	cout << ans << '\n';

	cin >> q;

	while(q--){
		int t, v; cin >> t >> v;
		if (t == 1){
			int k; cin >> k;
			int u = find(1, 1, n+1, 1, st[v], st[v]);
			remove(u);
			a[v] = k;
			add(v);
			add(u);
		}
		else{
			int u = find(1, 1, n+1, 1, st[v], st[v]);
			remove(u);
			remove(v);
			add(u);
		}
		cout << (cnt == 0? ans : 0) << '\n';
	}


	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 35840 KB Output is correct
2 Correct 233 ms 35796 KB Output is correct
3 Correct 248 ms 35880 KB Output is correct
4 Correct 231 ms 35780 KB Output is correct
5 Correct 221 ms 31884 KB Output is correct
6 Correct 92 ms 16456 KB Output is correct
7 Correct 95 ms 16136 KB Output is correct
8 Correct 98 ms 16260 KB Output is correct
9 Correct 209 ms 28112 KB Output is correct
10 Correct 245 ms 28128 KB Output is correct
11 Correct 221 ms 28056 KB Output is correct
12 Correct 210 ms 27440 KB Output is correct
13 Correct 257 ms 34540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 16024 KB Output is correct
2 Correct 102 ms 16016 KB Output is correct
3 Correct 119 ms 16028 KB Output is correct
4 Correct 97 ms 15984 KB Output is correct
5 Correct 94 ms 16076 KB Output is correct
6 Correct 93 ms 16176 KB Output is correct
7 Correct 95 ms 16172 KB Output is correct
8 Correct 111 ms 16168 KB Output is correct
9 Correct 93 ms 16332 KB Output is correct
10 Correct 112 ms 16364 KB Output is correct
11 Correct 100 ms 16352 KB Output is correct
12 Correct 96 ms 16332 KB Output is correct
13 Correct 102 ms 16300 KB Output is correct
14 Correct 101 ms 16332 KB Output is correct
15 Correct 131 ms 16584 KB Output is correct
16 Correct 107 ms 16332 KB Output is correct
17 Correct 101 ms 16444 KB Output is correct
18 Correct 99 ms 16244 KB Output is correct
19 Correct 97 ms 16288 KB Output is correct
20 Correct 90 ms 16140 KB Output is correct
21 Correct 90 ms 16212 KB Output is correct
22 Correct 91 ms 16080 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 41832 KB Output is correct
2 Correct 303 ms 42272 KB Output is correct
3 Correct 245 ms 42572 KB Output is correct
4 Correct 308 ms 43284 KB Output is correct
5 Correct 452 ms 40944 KB Output is correct
6 Correct 103 ms 16488 KB Output is correct
7 Correct 104 ms 16324 KB Output is correct
8 Correct 109 ms 16352 KB Output is correct
9 Correct 418 ms 36776 KB Output is correct
10 Correct 383 ms 36256 KB Output is correct
11 Correct 365 ms 36188 KB Output is correct
12 Correct 379 ms 36516 KB Output is correct
13 Correct 435 ms 55180 KB Output is correct
14 Correct 439 ms 55128 KB Output is correct
15 Correct 457 ms 55160 KB Output is correct
16 Correct 445 ms 55116 KB Output is correct
17 Correct 428 ms 55176 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 38728 KB Output is correct
2 Correct 761 ms 38748 KB Output is correct
3 Correct 778 ms 38840 KB Output is correct
4 Correct 622 ms 38816 KB Output is correct
5 Correct 586 ms 37796 KB Output is correct
6 Correct 606 ms 38664 KB Output is correct
7 Correct 449 ms 29012 KB Output is correct
8 Correct 535 ms 29328 KB Output is correct
9 Correct 782 ms 38788 KB Output is correct
10 Correct 610 ms 38912 KB Output is correct
11 Correct 601 ms 38996 KB Output is correct
12 Correct 484 ms 29224 KB Output is correct
13 Correct 385 ms 25212 KB Output is correct
14 Correct 392 ms 27480 KB Output is correct
15 Correct 792 ms 27852 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 35840 KB Output is correct
2 Correct 233 ms 35796 KB Output is correct
3 Correct 248 ms 35880 KB Output is correct
4 Correct 231 ms 35780 KB Output is correct
5 Correct 221 ms 31884 KB Output is correct
6 Correct 92 ms 16456 KB Output is correct
7 Correct 95 ms 16136 KB Output is correct
8 Correct 98 ms 16260 KB Output is correct
9 Correct 209 ms 28112 KB Output is correct
10 Correct 245 ms 28128 KB Output is correct
11 Correct 221 ms 28056 KB Output is correct
12 Correct 210 ms 27440 KB Output is correct
13 Correct 257 ms 34540 KB Output is correct
14 Correct 94 ms 16024 KB Output is correct
15 Correct 102 ms 16016 KB Output is correct
16 Correct 119 ms 16028 KB Output is correct
17 Correct 97 ms 15984 KB Output is correct
18 Correct 94 ms 16076 KB Output is correct
19 Correct 93 ms 16176 KB Output is correct
20 Correct 95 ms 16172 KB Output is correct
21 Correct 111 ms 16168 KB Output is correct
22 Correct 93 ms 16332 KB Output is correct
23 Correct 112 ms 16364 KB Output is correct
24 Correct 100 ms 16352 KB Output is correct
25 Correct 96 ms 16332 KB Output is correct
26 Correct 102 ms 16300 KB Output is correct
27 Correct 101 ms 16332 KB Output is correct
28 Correct 131 ms 16584 KB Output is correct
29 Correct 107 ms 16332 KB Output is correct
30 Correct 101 ms 16444 KB Output is correct
31 Correct 99 ms 16244 KB Output is correct
32 Correct 97 ms 16288 KB Output is correct
33 Correct 90 ms 16140 KB Output is correct
34 Correct 90 ms 16212 KB Output is correct
35 Correct 91 ms 16080 KB Output is correct
36 Correct 218 ms 41832 KB Output is correct
37 Correct 303 ms 42272 KB Output is correct
38 Correct 245 ms 42572 KB Output is correct
39 Correct 308 ms 43284 KB Output is correct
40 Correct 452 ms 40944 KB Output is correct
41 Correct 103 ms 16488 KB Output is correct
42 Correct 104 ms 16324 KB Output is correct
43 Correct 109 ms 16352 KB Output is correct
44 Correct 418 ms 36776 KB Output is correct
45 Correct 383 ms 36256 KB Output is correct
46 Correct 365 ms 36188 KB Output is correct
47 Correct 379 ms 36516 KB Output is correct
48 Correct 435 ms 55180 KB Output is correct
49 Correct 439 ms 55128 KB Output is correct
50 Correct 457 ms 55160 KB Output is correct
51 Correct 445 ms 55116 KB Output is correct
52 Correct 428 ms 55176 KB Output is correct
53 Correct 709 ms 38728 KB Output is correct
54 Correct 761 ms 38748 KB Output is correct
55 Correct 778 ms 38840 KB Output is correct
56 Correct 622 ms 38816 KB Output is correct
57 Correct 586 ms 37796 KB Output is correct
58 Correct 606 ms 38664 KB Output is correct
59 Correct 449 ms 29012 KB Output is correct
60 Correct 535 ms 29328 KB Output is correct
61 Correct 782 ms 38788 KB Output is correct
62 Correct 610 ms 38912 KB Output is correct
63 Correct 601 ms 38996 KB Output is correct
64 Correct 484 ms 29224 KB Output is correct
65 Correct 385 ms 25212 KB Output is correct
66 Correct 392 ms 27480 KB Output is correct
67 Correct 792 ms 27852 KB Output is correct
68 Correct 95 ms 15944 KB Output is correct
69 Correct 98 ms 16012 KB Output is correct
70 Correct 694 ms 46808 KB Output is correct
71 Correct 754 ms 46616 KB Output is correct
72 Correct 713 ms 46688 KB Output is correct
73 Correct 717 ms 46692 KB Output is correct
74 Correct 682 ms 46416 KB Output is correct
75 Correct 700 ms 42640 KB Output is correct
76 Correct 540 ms 38848 KB Output is correct
77 Correct 593 ms 38564 KB Output is correct
78 Correct 581 ms 37568 KB Output is correct
79 Correct 808 ms 42720 KB Output is correct
80 Correct 586 ms 41728 KB Output is correct
81 Correct 797 ms 42372 KB Output is correct
82 Correct 475 ms 33556 KB Output is correct
83 Correct 573 ms 39880 KB Output is correct
84 Correct 512 ms 39176 KB Output is correct
85 Correct 473 ms 39160 KB Output is correct