Submission #470171

# Submission time Handle Problem Language Result Execution time Memory
470171 2021-09-03T07:28:03 Z Sohsoh84 Sumtree (INOI20_sumtree) C++14
50 / 100
716 ms 93548 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) {
	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);
		F[ind] = 0;
		return;
	}

	ans = ans * val % MOD * (F[ind] == 0 ? 1 : 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;
}
# Verdict Execution time Memory Grader output
1 Correct 358 ms 80532 KB Output is correct
2 Correct 345 ms 80484 KB Output is correct
3 Correct 354 ms 80572 KB Output is correct
4 Correct 351 ms 80468 KB Output is correct
5 Correct 367 ms 76560 KB Output is correct
6 Correct 181 ms 48060 KB Output is correct
7 Correct 177 ms 47780 KB Output is correct
8 Correct 180 ms 47812 KB Output is correct
9 Correct 348 ms 72976 KB Output is correct
10 Correct 419 ms 72596 KB Output is correct
11 Correct 345 ms 72856 KB Output is correct
12 Correct 345 ms 71444 KB Output is correct
13 Correct 326 ms 78044 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 176 ms 47524 KB Output is correct
2 Correct 177 ms 47408 KB Output is correct
3 Correct 177 ms 47416 KB Output is correct
4 Correct 174 ms 47388 KB Output is correct
5 Correct 176 ms 47468 KB Output is correct
6 Correct 178 ms 47652 KB Output is correct
7 Correct 181 ms 47716 KB Output is correct
8 Correct 182 ms 47684 KB Output is correct
9 Correct 194 ms 47828 KB Output is correct
10 Correct 183 ms 47936 KB Output is correct
11 Correct 195 ms 47976 KB Output is correct
12 Correct 176 ms 47860 KB Output is correct
13 Correct 179 ms 47868 KB Output is correct
14 Correct 188 ms 47932 KB Output is correct
15 Correct 192 ms 48072 KB Output is correct
16 Correct 184 ms 47840 KB Output is correct
17 Correct 181 ms 47928 KB Output is correct
18 Correct 189 ms 47588 KB Output is correct
19 Correct 180 ms 47828 KB Output is correct
20 Correct 181 ms 47716 KB Output is correct
21 Correct 186 ms 47712 KB Output is correct
22 Correct 174 ms 47428 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 413 ms 82652 KB Output is correct
2 Correct 424 ms 83392 KB Output is correct
3 Correct 360 ms 83652 KB Output is correct
4 Correct 450 ms 84016 KB Output is correct
5 Correct 584 ms 80824 KB Output is correct
6 Correct 179 ms 48100 KB Output is correct
7 Correct 177 ms 47752 KB Output is correct
8 Correct 179 ms 47880 KB Output is correct
9 Correct 536 ms 76996 KB Output is correct
10 Correct 511 ms 76808 KB Output is correct
11 Correct 485 ms 76628 KB Output is correct
12 Correct 567 ms 77252 KB Output is correct
13 Correct 582 ms 93476 KB Output is correct
14 Correct 573 ms 93436 KB Output is correct
15 Correct 582 ms 93380 KB Output is correct
16 Correct 571 ms 93336 KB Output is correct
17 Correct 576 ms 93548 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 693 ms 78132 KB Output is correct
2 Correct 655 ms 77936 KB Output is correct
3 Correct 676 ms 78148 KB Output is correct
4 Correct 670 ms 78116 KB Output is correct
5 Correct 646 ms 76360 KB Output is correct
6 Correct 646 ms 77892 KB Output is correct
7 Correct 525 ms 63720 KB Output is correct
8 Correct 586 ms 63732 KB Output is correct
9 Correct 716 ms 77940 KB Output is correct
10 Correct 655 ms 77952 KB Output is correct
11 Correct 644 ms 77928 KB Output is correct
12 Correct 528 ms 63784 KB Output is correct
13 Incorrect 456 ms 61252 KB Output isn't correct
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 358 ms 80532 KB Output is correct
2 Correct 345 ms 80484 KB Output is correct
3 Correct 354 ms 80572 KB Output is correct
4 Correct 351 ms 80468 KB Output is correct
5 Correct 367 ms 76560 KB Output is correct
6 Correct 181 ms 48060 KB Output is correct
7 Correct 177 ms 47780 KB Output is correct
8 Correct 180 ms 47812 KB Output is correct
9 Correct 348 ms 72976 KB Output is correct
10 Correct 419 ms 72596 KB Output is correct
11 Correct 345 ms 72856 KB Output is correct
12 Correct 345 ms 71444 KB Output is correct
13 Correct 326 ms 78044 KB Output is correct
14 Correct 176 ms 47524 KB Output is correct
15 Correct 177 ms 47408 KB Output is correct
16 Correct 177 ms 47416 KB Output is correct
17 Correct 174 ms 47388 KB Output is correct
18 Correct 176 ms 47468 KB Output is correct
19 Correct 178 ms 47652 KB Output is correct
20 Correct 181 ms 47716 KB Output is correct
21 Correct 182 ms 47684 KB Output is correct
22 Correct 194 ms 47828 KB Output is correct
23 Correct 183 ms 47936 KB Output is correct
24 Correct 195 ms 47976 KB Output is correct
25 Correct 176 ms 47860 KB Output is correct
26 Correct 179 ms 47868 KB Output is correct
27 Correct 188 ms 47932 KB Output is correct
28 Correct 192 ms 48072 KB Output is correct
29 Correct 184 ms 47840 KB Output is correct
30 Correct 181 ms 47928 KB Output is correct
31 Correct 189 ms 47588 KB Output is correct
32 Correct 180 ms 47828 KB Output is correct
33 Correct 181 ms 47716 KB Output is correct
34 Correct 186 ms 47712 KB Output is correct
35 Correct 174 ms 47428 KB Output is correct
36 Correct 413 ms 82652 KB Output is correct
37 Correct 424 ms 83392 KB Output is correct
38 Correct 360 ms 83652 KB Output is correct
39 Correct 450 ms 84016 KB Output is correct
40 Correct 584 ms 80824 KB Output is correct
41 Correct 179 ms 48100 KB Output is correct
42 Correct 177 ms 47752 KB Output is correct
43 Correct 179 ms 47880 KB Output is correct
44 Correct 536 ms 76996 KB Output is correct
45 Correct 511 ms 76808 KB Output is correct
46 Correct 485 ms 76628 KB Output is correct
47 Correct 567 ms 77252 KB Output is correct
48 Correct 582 ms 93476 KB Output is correct
49 Correct 573 ms 93436 KB Output is correct
50 Correct 582 ms 93380 KB Output is correct
51 Correct 571 ms 93336 KB Output is correct
52 Correct 576 ms 93548 KB Output is correct
53 Correct 693 ms 78132 KB Output is correct
54 Correct 655 ms 77936 KB Output is correct
55 Correct 676 ms 78148 KB Output is correct
56 Correct 670 ms 78116 KB Output is correct
57 Correct 646 ms 76360 KB Output is correct
58 Correct 646 ms 77892 KB Output is correct
59 Correct 525 ms 63720 KB Output is correct
60 Correct 586 ms 63732 KB Output is correct
61 Correct 716 ms 77940 KB Output is correct
62 Correct 655 ms 77952 KB Output is correct
63 Correct 644 ms 77928 KB Output is correct
64 Correct 528 ms 63784 KB Output is correct
65 Incorrect 456 ms 61252 KB Output isn't correct
66 Halted 0 ms 0 KB -