oj.uz

Submission #469348

# Submission time Handle Problem Language Result Execution time Memory
469348 2021-08-31T14:29:17 Z sinamhdv Sumtree (INOI20_sumtree) C++11
50 / 100
 3000 ms 49988 KB 
// INOI20_sumtree
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 200100;
const int MAXF = 500100;
const int LOGN = 25;

inline int poww(int a, int b)
{
	int res = 1;
	for (; b; a = (ll)a * a % mod, b /= 2) if (b & 1) res = (ll)res * a % mod;
	return res;
}

int n, rt, q;
vector<int> adj[MAXN];
int bad, ans;
int sttime[MAXN], fntime[MAXN], timer, h[MAXN];
int lbl[MAXN], val[MAXN], cnt[MAXN];
int lpar[LOGN][MAXN];
int fact[MAXF], finv[MAXF];

inline int comb(int n, int k)
{
	return (fact[n] * (ll)finv[k] % mod) * finv[n - k] % mod;
}

void dfs1(int v)
{
	sttime[v] = timer++;
	for (int u : adj[v]) if (u != lpar[0][v])
	{
		lpar[0][u] = v;
		h[u] = h[v] + 1, dfs1(u);
	}
	fntime[v] = timer;
}

struct FEN
{
	ll fen[MAXN];

	inline void addind(int i, ll x)
	{
		for (i++; i < MAXN; i += i & -i) fen[i] += x;
	}

	inline ll pget(int i)
	{
		ll res = 0;
		for (i++; i > 0; i -= i & -i) res += fen[i];
		return res;
	}

	inline ll get(int l, int r)
	{
		if (l > r) return 0;
		return pget(r) - pget(l - 1);
	}

	inline void add(int l, int r, ll x)
	{
		addind(l, x);
		addind(r + 1, -x);
	}

} valfen, ancfen;

struct node
{
	int mn, mncnt, lz;
};

struct SEG
{
	int seg[4 * MAXN];

	void rset(int L, int R, int x)//, int v = 1, int l = 0, int r = n - 1)
	{
		int mn = *min_element(seg + L, seg + R + 1);
		FOR(i, L, R + 1) if (seg[i] == mn) seg[i] = x;
	}

	pii getmin(int L, int R)
	{
		int mn = *min_element(seg + L, seg + R + 1);
		int cnt = 0;
		FOR(i, L, R + 1) if (seg[i] == mn) cnt++;
		return {mn, cnt};
	}

} seg;

inline int getpar(int x, int d)
{
	FOR(i, 0, LOGN) if (d >> i & 1) x = lpar[i][x];
	return x;
}

inline void addans(int i)
{
	if (val[i] < 0) bad++;
	else ans = (ll)ans * comb(val[i] + cnt[i] - 1, cnt[i] - 1) % mod;
}

inline void remans(int i)
{
	if (val[i] < 0) bad--;
	else ans = (ll)ans * poww(comb(val[i] + cnt[i] - 1, cnt[i] - 1), mod - 2) % mod;
}

inline void updateval(int v)
{
	ll nw = lbl[v] - valfen.get(sttime[v] + 1, fntime[v] - 1);
	valfen.addind(sttime[v], nw - val[v]);
	val[v] = nw;
}

inline int findanc(int v)
{
	int l = 0, r = h[v] + 1;
	int cur = ancfen.pget(sttime[v]);
	while (r - l > 1)
	{
		int mid = (r + l) / 2;
		int x = getpar(v, mid);
		if (ancfen.pget(sttime[x]) == cur) l = mid;
		else r = mid;
	}
	return getpar(v, l);
}

int32_t main(void)
{
	fast_io;

	fact[0] = 1;
	FOR(i, 1, MAXF) fact[i] = fact[i - 1] * (ll)i % mod;
	finv[MAXF - 1] = poww(fact[MAXF - 1], mod - 2);
	for (int i = MAXF - 2; i >= 0; i--) finv[i] = (ll)finv[i + 1] * (i + 1) % mod;

	cin >> n >> rt;
	FOR(i, 0, n - 1)
	{
		int x, y;
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	dfs1(1);

	FOR(i, 1, LOGN) FOR(j, 1, n + 1) lpar[i][j] = lpar[i - 1][lpar[i - 1][j]];

	ans = comb(n + rt - 1, n - 1);
	cout << ans << endl;
	ancfen.add(0, n - 1, 1);
	lbl[1] = val[1] = rt;
	cnt[1] = n;

	cin >> q;
	while (q--)
	{
		int op, v;
		cin >> op >> v;
		if (op == 1)	// add
		{
			int x;
			cin >> x;
			lbl[v] = x;

			// update anc
			int l = findanc(v);
			ancfen.add(sttime[v], fntime[v] - 1, 1);

			remans(l);

			// update cnt
			pii p = seg.getmin(sttime[v], fntime[v] - 1);
			seg.rset(sttime[v], fntime[v] - 1, sttime[v]);
			cnt[l] -= p.sc;
			cnt[v] += p.sc;

			// update val
			updateval(v);
			updateval(l);

			addans(v);
			addans(l);
		}
		else	// rem
		{
			ancfen.add(sttime[v], fntime[v] - 1, -1);
			int l = findanc(v);

			remans(l);
			remans(v);

			pii p = seg.getmin(sttime[v], fntime[v] - 1);
			seg.rset(sttime[v], fntime[v] - 1, sttime[l]);
			cnt[l] += p.sc;
			cnt[v] = 0;

			valfen.addind(sttime[v], -val[v]);
			lbl[v] = val[v] = 0;
			updateval(l);

			addans(l);
		}

		ans = (mod + ans % mod) % mod;
		if (bad) cout << "0\n";
		else cout << ans << endl;
	}

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 43568 KB Output is correct
2 Correct 146 ms 43588 KB Output is correct
3 Correct 154 ms 43588 KB Output is correct
4 Correct 156 ms 43548 KB Output is correct
5 Correct 131 ms 40388 KB Output is correct
6 Correct 13 ms 9676 KB Output is correct
7 Correct 13 ms 9564 KB Output is correct
8 Correct 13 ms 9548 KB Output is correct
9 Correct 156 ms 37464 KB Output is correct
10 Correct 159 ms 37444 KB Output is correct
11 Correct 162 ms 37524 KB Output is correct
12 Correct 149 ms 36140 KB Output is correct
13 Correct 144 ms 40772 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9164 KB Output is correct
2 Correct 12 ms 9164 KB Output is correct
3 Correct 12 ms 9164 KB Output is correct
4 Correct 12 ms 9076 KB Output is correct
5 Correct 14 ms 9164 KB Output is correct
6 Correct 16 ms 9548 KB Output is correct
7 Correct 16 ms 9548 KB Output is correct
8 Correct 16 ms 9564 KB Output is correct
9 Correct 18 ms 9768 KB Output is correct
10 Correct 25 ms 9804 KB Output is correct
11 Correct 24 ms 9804 KB Output is correct
12 Correct 14 ms 9748 KB Output is correct
13 Correct 22 ms 9804 KB Output is correct
14 Correct 20 ms 9688 KB Output is correct
15 Correct 40 ms 9932 KB Output is correct
16 Correct 17 ms 9676 KB Output is correct
17 Correct 21 ms 9720 KB Output is correct
18 Correct 24 ms 9420 KB Output is correct
19 Correct 17 ms 9680 KB Output is correct
20 Correct 16 ms 9468 KB Output is correct
21 Correct 15 ms 9548 KB Output is correct
22 Correct 12 ms 9164 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1550 ms 49324 KB Output is correct
2 Execution timed out 3094 ms 49628 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 794 ms 46324 KB Output is correct
2 Correct 718 ms 49900 KB Output is correct
3 Correct 629 ms 49960 KB Output is correct
4 Correct 751 ms 49988 KB Output is correct
5 Correct 686 ms 48112 KB Output is correct
6 Correct 630 ms 49864 KB Output is correct
7 Correct 480 ms 31292 KB Output is correct
8 Correct 696 ms 31592 KB Output is correct
9 Correct 834 ms 49876 KB Output is correct
10 Correct 645 ms 49936 KB Output is correct
11 Correct 664 ms 49800 KB Output is correct
12 Correct 533 ms 31556 KB Output is correct
13 Correct 439 ms 27696 KB Output is correct
14 Correct 479 ms 29956 KB Output is correct
15 Correct 591 ms 30156 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 43568 KB Output is correct
2 Correct 146 ms 43588 KB Output is correct
3 Correct 154 ms 43588 KB Output is correct
4 Correct 156 ms 43548 KB Output is correct
5 Correct 131 ms 40388 KB Output is correct
6 Correct 13 ms 9676 KB Output is correct
7 Correct 13 ms 9564 KB Output is correct
8 Correct 13 ms 9548 KB Output is correct
9 Correct 156 ms 37464 KB Output is correct
10 Correct 159 ms 37444 KB Output is correct
11 Correct 162 ms 37524 KB Output is correct
12 Correct 149 ms 36140 KB Output is correct
13 Correct 144 ms 40772 KB Output is correct
14 Correct 13 ms 9164 KB Output is correct
15 Correct 12 ms 9164 KB Output is correct
16 Correct 12 ms 9164 KB Output is correct
17 Correct 12 ms 9076 KB Output is correct
18 Correct 14 ms 9164 KB Output is correct
19 Correct 16 ms 9548 KB Output is correct
20 Correct 16 ms 9548 KB Output is correct
21 Correct 16 ms 9564 KB Output is correct
22 Correct 18 ms 9768 KB Output is correct
23 Correct 25 ms 9804 KB Output is correct
24 Correct 24 ms 9804 KB Output is correct
25 Correct 14 ms 9748 KB Output is correct
26 Correct 22 ms 9804 KB Output is correct
27 Correct 20 ms 9688 KB Output is correct
28 Correct 40 ms 9932 KB Output is correct
29 Correct 17 ms 9676 KB Output is correct
30 Correct 21 ms 9720 KB Output is correct
31 Correct 24 ms 9420 KB Output is correct
32 Correct 17 ms 9680 KB Output is correct
33 Correct 16 ms 9468 KB Output is correct
34 Correct 15 ms 9548 KB Output is correct
35 Correct 12 ms 9164 KB Output is correct
36 Correct 1550 ms 49324 KB Output is correct
37 Execution timed out 3094 ms 49628 KB Time limit exceeded
38 Halted 0 ms 0 KB -