답안 #470168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
470168 2021-09-03T07:23:24 Z Sohsoh84 Sumtree (INOI20_sumtree) C++14
50 / 100
754 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);
		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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 354 ms 80444 KB Output is correct
2 Correct 374 ms 80360 KB Output is correct
3 Correct 362 ms 80404 KB Output is correct
4 Correct 351 ms 80320 KB Output is correct
5 Correct 338 ms 76356 KB Output is correct
6 Correct 178 ms 48056 KB Output is correct
7 Correct 188 ms 47812 KB Output is correct
8 Correct 187 ms 47820 KB Output is correct
9 Correct 368 ms 72716 KB Output is correct
10 Correct 369 ms 72728 KB Output is correct
11 Correct 371 ms 72644 KB Output is correct
12 Correct 378 ms 71468 KB Output is correct
13 Correct 389 ms 77752 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 47452 KB Output is correct
2 Correct 186 ms 47484 KB Output is correct
3 Correct 186 ms 47452 KB Output is correct
4 Correct 180 ms 47452 KB Output is correct
5 Correct 188 ms 47532 KB Output is correct
6 Correct 185 ms 47812 KB Output is correct
7 Correct 195 ms 47856 KB Output is correct
8 Correct 186 ms 47772 KB Output is correct
9 Correct 190 ms 47924 KB Output is correct
10 Correct 187 ms 47952 KB Output is correct
11 Correct 189 ms 47940 KB Output is correct
12 Correct 181 ms 47904 KB Output is correct
13 Correct 186 ms 47940 KB Output is correct
14 Correct 188 ms 47920 KB Output is correct
15 Correct 184 ms 48108 KB Output is correct
16 Correct 185 ms 48044 KB Output is correct
17 Correct 187 ms 47976 KB Output is correct
18 Correct 186 ms 47708 KB Output is correct
19 Correct 183 ms 47992 KB Output is correct
20 Correct 185 ms 47716 KB Output is correct
21 Correct 187 ms 47680 KB Output is correct
22 Correct 180 ms 47556 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 386 ms 82884 KB Output is correct
2 Correct 471 ms 83328 KB Output is correct
3 Correct 383 ms 83656 KB Output is correct
4 Correct 491 ms 84060 KB Output is correct
5 Correct 577 ms 80784 KB Output is correct
6 Correct 182 ms 48312 KB Output is correct
7 Correct 186 ms 47784 KB Output is correct
8 Correct 181 ms 47940 KB Output is correct
9 Correct 594 ms 77152 KB Output is correct
10 Correct 539 ms 76740 KB Output is correct
11 Correct 516 ms 76712 KB Output is correct
12 Correct 567 ms 77340 KB Output is correct
13 Correct 576 ms 93396 KB Output is correct
14 Correct 584 ms 93508 KB Output is correct
15 Correct 584 ms 93388 KB Output is correct
16 Correct 576 ms 93548 KB Output is correct
17 Correct 586 ms 93504 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 700 ms 78276 KB Output is correct
2 Correct 696 ms 77884 KB Output is correct
3 Correct 726 ms 78080 KB Output is correct
4 Correct 754 ms 78040 KB Output is correct
5 Correct 720 ms 76520 KB Output is correct
6 Correct 689 ms 78020 KB Output is correct
7 Correct 556 ms 63812 KB Output is correct
8 Correct 604 ms 63856 KB Output is correct
9 Correct 727 ms 78092 KB Output is correct
10 Correct 706 ms 78020 KB Output is correct
11 Correct 753 ms 78120 KB Output is correct
12 Correct 547 ms 63812 KB Output is correct
13 Incorrect 457 ms 61124 KB Output isn't correct
14 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 354 ms 80444 KB Output is correct
2 Correct 374 ms 80360 KB Output is correct
3 Correct 362 ms 80404 KB Output is correct
4 Correct 351 ms 80320 KB Output is correct
5 Correct 338 ms 76356 KB Output is correct
6 Correct 178 ms 48056 KB Output is correct
7 Correct 188 ms 47812 KB Output is correct
8 Correct 187 ms 47820 KB Output is correct
9 Correct 368 ms 72716 KB Output is correct
10 Correct 369 ms 72728 KB Output is correct
11 Correct 371 ms 72644 KB Output is correct
12 Correct 378 ms 71468 KB Output is correct
13 Correct 389 ms 77752 KB Output is correct
14 Correct 179 ms 47452 KB Output is correct
15 Correct 186 ms 47484 KB Output is correct
16 Correct 186 ms 47452 KB Output is correct
17 Correct 180 ms 47452 KB Output is correct
18 Correct 188 ms 47532 KB Output is correct
19 Correct 185 ms 47812 KB Output is correct
20 Correct 195 ms 47856 KB Output is correct
21 Correct 186 ms 47772 KB Output is correct
22 Correct 190 ms 47924 KB Output is correct
23 Correct 187 ms 47952 KB Output is correct
24 Correct 189 ms 47940 KB Output is correct
25 Correct 181 ms 47904 KB Output is correct
26 Correct 186 ms 47940 KB Output is correct
27 Correct 188 ms 47920 KB Output is correct
28 Correct 184 ms 48108 KB Output is correct
29 Correct 185 ms 48044 KB Output is correct
30 Correct 187 ms 47976 KB Output is correct
31 Correct 186 ms 47708 KB Output is correct
32 Correct 183 ms 47992 KB Output is correct
33 Correct 185 ms 47716 KB Output is correct
34 Correct 187 ms 47680 KB Output is correct
35 Correct 180 ms 47556 KB Output is correct
36 Correct 386 ms 82884 KB Output is correct
37 Correct 471 ms 83328 KB Output is correct
38 Correct 383 ms 83656 KB Output is correct
39 Correct 491 ms 84060 KB Output is correct
40 Correct 577 ms 80784 KB Output is correct
41 Correct 182 ms 48312 KB Output is correct
42 Correct 186 ms 47784 KB Output is correct
43 Correct 181 ms 47940 KB Output is correct
44 Correct 594 ms 77152 KB Output is correct
45 Correct 539 ms 76740 KB Output is correct
46 Correct 516 ms 76712 KB Output is correct
47 Correct 567 ms 77340 KB Output is correct
48 Correct 576 ms 93396 KB Output is correct
49 Correct 584 ms 93508 KB Output is correct
50 Correct 584 ms 93388 KB Output is correct
51 Correct 576 ms 93548 KB Output is correct
52 Correct 586 ms 93504 KB Output is correct
53 Correct 700 ms 78276 KB Output is correct
54 Correct 696 ms 77884 KB Output is correct
55 Correct 726 ms 78080 KB Output is correct
56 Correct 754 ms 78040 KB Output is correct
57 Correct 720 ms 76520 KB Output is correct
58 Correct 689 ms 78020 KB Output is correct
59 Correct 556 ms 63812 KB Output is correct
60 Correct 604 ms 63856 KB Output is correct
61 Correct 727 ms 78092 KB Output is correct
62 Correct 706 ms 78020 KB Output is correct
63 Correct 753 ms 78120 KB Output is correct
64 Correct 547 ms 63812 KB Output is correct
65 Incorrect 457 ms 61124 KB Output isn't correct
66 Halted 0 ms 0 KB -