oj.uz

Submission #470173

# Submission time Handle Problem Language Result Execution time Memory
470173 2021-09-03T07:32:09 Z Sohsoh84 Sumtree (INOI20_sumtree) C++14
100 / 100
 880 ms 93636 KB 
// orz
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;
const ll LOG = 20;

struct Fenwick {
	int fen[MAXN];
	Fenwick() {}

	inline void add(int ind, int val) {
		for (++ind; ind < MAXN; ind += ind & -ind)
			fen[ind] += val;
	}

	inline int query(int ind) {
		int ans = 0;
		for (++ind; ind > 0; ind -= ind & -ind)
			ans += fen[ind];
		return ans;
	}

	inline void add(int l, int r, int val) {
		if (r < l) return;
		add(l, val);
		add(r + 1, -val);
	}


	inline int query(int l, int r) {
		if (r < l) return 0;
		return query(r) - query(l - 1);
	}

	inline void update(int ind, int val) {
		val -= query(ind, ind);
		add(ind, val);
	}
};


inline ll poww(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}

	return ans;
}

inline ll Inv(ll a) {
	if (a == 0) return 1;
	return poww(a, MOD - 2);
}

// R == 0 ?

set<int> Z;
int n, r, q, sub_g[MAXN], par[MAXN][LOG],
    tin[MAXN], tout[MAXN], T, H[MAXN], R[MAXN];
ll fact[MAXN], inv[MAXN], F[MAXN], ans = 1;
vector<int> adj[MAXN];
Fenwick s_fen, t_fen, p_fen;

void dfs(int v, int p) {
	sub_g[v] = 1;
	par[v][0] = p;
	H[v] = H[p] + 1;
	tin[v] = ++T;

	for (int u : adj[v])
		if (u != p)
			dfs(u, v), sub_g[v] += sub_g[u];
	tout[v] = T;
}

inline ll C(ll k, ll n) {
	if (k < 0 || k > n) return 0;
	return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}

inline void update(int ind, ll val) {
	if (F[ind] == 0) Z.erase(ind);
	
	if (val == 0) {
		Z.insert(ind);
		ans = ans * Inv(F[ind]) % MOD;
		F[ind] = 0;
		return;
	}

	ans = ans * val % MOD * Inv(F[ind]) % MOD;
	F[ind] = val;
}

inline int Par(int v) {
	int t = p_fen.query(tin[v]);
	for (int i = LOG - 1; i >= 0; i--)
		if (p_fen.query(tin[par[v][i]]) == t)
			v = par[v][i];
	return par[v][0];
}

inline void add(int v, int r) {
	R[v] = r;
	p_fen.add(tin[v] + 1, tout[v], 1);
	r -= t_fen.query(tin[v] + 1, tout[v]);
	t_fen.add(tin[v], r);
	
	int s = sub_g[v] - s_fen.query(tin[v] + 1, tout[v]);
	s_fen.add(tin[v], s);
	
	update(v, C(s - 1, s + r - 1));
}

inline void recalc(int v) {
	int r = R[v];
	r -= t_fen.query(tin[v] + 1, tout[v]);
	t_fen.update(tin[v], r);
	
	int s = sub_g[v] - s_fen.query(tin[v] + 1, tout[v]);
	s_fen.update(tin[v], s);
	
	update(v, C(s - 1, s + r - 1));
}

inline void remove(int v) {
	p_fen.add(tin[v] + 1, tout[v], -1);
	s_fen.update(tin[v], 0);
	t_fen.update(tin[v], 0);
	R[v] = 1;
	update(v, 1);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	fact[0] = inv[0] = 1;
	for (int i = 1; i < MAXN; i++) 
		fact[i] = fact[i - 1] * i % MOD, inv[i] = Inv(fact[i]);
	fill(F, F + MAXN, 1);

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


	dfs(1, 0);
	for (int i = 1; i < LOG; i++)
		for (int v = 1; v <= n; v++)
			par[v][i] = par[par[v][i - 1]][i - 1];
	
	add(1, r);

	cout << (Z.empty() ? ans : 0) << endl;
	cin >> q;
	while (q--) {
		int c;
		cin >> c;
		if (c == 1) {
			int v, u, p;
			cin >> v >> u;
			add(v, u);
			p = Par(v);
			recalc(p);
		} else {
			int v, p;
			cin >> v;
			p = Par(v);
		
			remove(v);
			recalc(p);
		}

		cout << (Z.empty() ? ans : 0) << endl;
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 80580 KB Output is correct
2 Correct 354 ms 80776 KB Output is correct
3 Correct 352 ms 80568 KB Output is correct
4 Correct 347 ms 80748 KB Output is correct
5 Correct 323 ms 76684 KB Output is correct
6 Correct 177 ms 48184 KB Output is correct
7 Correct 180 ms 47776 KB Output is correct
8 Correct 174 ms 47828 KB Output is correct
9 Correct 364 ms 73132 KB Output is correct
10 Correct 340 ms 72692 KB Output is correct
11 Correct 342 ms 72940 KB Output is correct
12 Correct 369 ms 71588 KB Output is correct
13 Correct 323 ms 78000 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 47372 KB Output is correct
2 Correct 176 ms 47428 KB Output is correct
3 Correct 177 ms 47448 KB Output is correct
4 Correct 178 ms 47428 KB Output is correct
5 Correct 179 ms 47476 KB Output is correct
6 Correct 181 ms 47684 KB Output is correct
7 Correct 180 ms 47808 KB Output is correct
8 Correct 184 ms 47756 KB Output is correct
9 Correct 184 ms 47916 KB Output is correct
10 Correct 179 ms 47940 KB Output is correct
11 Correct 179 ms 48012 KB Output is correct
12 Correct 175 ms 47940 KB Output is correct
13 Correct 180 ms 47968 KB Output is correct
14 Correct 181 ms 47940 KB Output is correct
15 Correct 180 ms 48076 KB Output is correct
16 Correct 178 ms 47940 KB Output is correct
17 Correct 182 ms 47864 KB Output is correct
18 Correct 182 ms 47748 KB Output is correct
19 Correct 184 ms 47868 KB Output is correct
20 Correct 177 ms 47684 KB Output is correct
21 Correct 180 ms 47872 KB Output is correct
22 Correct 180 ms 47424 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 83008 KB Output is correct
2 Correct 399 ms 83428 KB Output is correct
3 Correct 366 ms 83880 KB Output is correct
4 Correct 441 ms 84248 KB Output is correct
5 Correct 572 ms 80964 KB Output is correct
6 Correct 179 ms 48068 KB Output is correct
7 Correct 177 ms 47812 KB Output is correct
8 Correct 179 ms 47920 KB Output is correct
9 Correct 562 ms 77148 KB Output is correct
10 Correct 498 ms 76868 KB Output is correct
11 Correct 492 ms 76916 KB Output is correct
12 Correct 535 ms 77380 KB Output is correct
13 Correct 569 ms 93488 KB Output is correct
14 Correct 574 ms 93556 KB Output is correct
15 Correct 572 ms 93636 KB Output is correct
16 Correct 571 ms 93512 KB Output is correct
17 Correct 577 ms 93508 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 78332 KB Output is correct
2 Correct 676 ms 78148 KB Output is correct
3 Correct 662 ms 78276 KB Output is correct
4 Correct 673 ms 78084 KB Output is correct
5 Correct 682 ms 76652 KB Output is correct
6 Correct 649 ms 78244 KB Output is correct
7 Correct 524 ms 64064 KB Output is correct
8 Correct 564 ms 64088 KB Output is correct
9 Correct 691 ms 78268 KB Output is correct
10 Correct 667 ms 78160 KB Output is correct
11 Correct 647 ms 78208 KB Output is correct
12 Correct 550 ms 63964 KB Output is correct
13 Correct 476 ms 61400 KB Output is correct
14 Correct 499 ms 65372 KB Output is correct
15 Correct 498 ms 65220 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 80580 KB Output is correct
2 Correct 354 ms 80776 KB Output is correct
3 Correct 352 ms 80568 KB Output is correct
4 Correct 347 ms 80748 KB Output is correct
5 Correct 323 ms 76684 KB Output is correct
6 Correct 177 ms 48184 KB Output is correct
7 Correct 180 ms 47776 KB Output is correct
8 Correct 174 ms 47828 KB Output is correct
9 Correct 364 ms 73132 KB Output is correct
10 Correct 340 ms 72692 KB Output is correct
11 Correct 342 ms 72940 KB Output is correct
12 Correct 369 ms 71588 KB Output is correct
13 Correct 323 ms 78000 KB Output is correct
14 Correct 175 ms 47372 KB Output is correct
15 Correct 176 ms 47428 KB Output is correct
16 Correct 177 ms 47448 KB Output is correct
17 Correct 178 ms 47428 KB Output is correct
18 Correct 179 ms 47476 KB Output is correct
19 Correct 181 ms 47684 KB Output is correct
20 Correct 180 ms 47808 KB Output is correct
21 Correct 184 ms 47756 KB Output is correct
22 Correct 184 ms 47916 KB Output is correct
23 Correct 179 ms 47940 KB Output is correct
24 Correct 179 ms 48012 KB Output is correct
25 Correct 175 ms 47940 KB Output is correct
26 Correct 180 ms 47968 KB Output is correct
27 Correct 181 ms 47940 KB Output is correct
28 Correct 180 ms 48076 KB Output is correct
29 Correct 178 ms 47940 KB Output is correct
30 Correct 182 ms 47864 KB Output is correct
31 Correct 182 ms 47748 KB Output is correct
32 Correct 184 ms 47868 KB Output is correct
33 Correct 177 ms 47684 KB Output is correct
34 Correct 180 ms 47872 KB Output is correct
35 Correct 180 ms 47424 KB Output is correct
36 Correct 367 ms 83008 KB Output is correct
37 Correct 399 ms 83428 KB Output is correct
38 Correct 366 ms 83880 KB Output is correct
39 Correct 441 ms 84248 KB Output is correct
40 Correct 572 ms 80964 KB Output is correct
41 Correct 179 ms 48068 KB Output is correct
42 Correct 177 ms 47812 KB Output is correct
43 Correct 179 ms 47920 KB Output is correct
44 Correct 562 ms 77148 KB Output is correct
45 Correct 498 ms 76868 KB Output is correct
46 Correct 492 ms 76916 KB Output is correct
47 Correct 535 ms 77380 KB Output is correct
48 Correct 569 ms 93488 KB Output is correct
49 Correct 574 ms 93556 KB Output is correct
50 Correct 572 ms 93636 KB Output is correct
51 Correct 571 ms 93512 KB Output is correct
52 Correct 577 ms 93508 KB Output is correct
53 Correct 707 ms 78332 KB Output is correct
54 Correct 676 ms 78148 KB Output is correct
55 Correct 662 ms 78276 KB Output is correct
56 Correct 673 ms 78084 KB Output is correct
57 Correct 682 ms 76652 KB Output is correct
58 Correct 649 ms 78244 KB Output is correct
59 Correct 524 ms 64064 KB Output is correct
60 Correct 564 ms 64088 KB Output is correct
61 Correct 691 ms 78268 KB Output is correct
62 Correct 667 ms 78160 KB Output is correct
63 Correct 647 ms 78208 KB Output is correct
64 Correct 550 ms 63964 KB Output is correct
65 Correct 476 ms 61400 KB Output is correct
66 Correct 499 ms 65372 KB Output is correct
67 Correct 498 ms 65220 KB Output is correct
68 Correct 177 ms 47352 KB Output is correct
69 Correct 176 ms 47420 KB Output is correct
70 Correct 793 ms 90100 KB Output is correct
71 Correct 824 ms 90228 KB Output is correct
72 Correct 880 ms 90112 KB Output is correct
73 Correct 817 ms 90120 KB Output is correct
74 Correct 838 ms 89880 KB Output is correct
75 Correct 824 ms 86320 KB Output is correct
76 Correct 677 ms 82336 KB Output is correct
77 Correct 715 ms 82308 KB Output is correct
78 Correct 741 ms 81108 KB Output is correct
79 Correct 809 ms 86220 KB Output is correct
80 Correct 781 ms 84776 KB Output is correct
81 Correct 827 ms 85912 KB Output is correct
82 Correct 601 ms 79556 KB Output is correct
83 Correct 660 ms 86728 KB Output is correct
84 Correct 640 ms 86168 KB Output is correct
85 Correct 671 ms 86048 KB Output is correct