oj.uz

Submission #469345

# Submission time Handle Problem Language Result Execution time Memory
469345 2021-08-31T14:22:52 Z sinamhdv Sumtree (INOI20_sumtree) C++11
10 / 100
 3000 ms 92280 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);
			if (p.fr == sttime[l])
			{
				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
		{
			// reset cnt & lbl & val
		}

		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 156 ms 45888 KB Output is correct
2 Correct 157 ms 45808 KB Output is correct
3 Correct 149 ms 45892 KB Output is correct
4 Correct 154 ms 46020 KB Output is correct
5 Correct 136 ms 42704 KB Output is correct
6 Correct 13 ms 9676 KB Output is correct
7 Correct 14 ms 9596 KB Output is correct
8 Correct 13 ms 9560 KB Output is correct
9 Correct 154 ms 39840 KB Output is correct
10 Correct 152 ms 39748 KB Output is correct
11 Correct 151 ms 39716 KB Output is correct
12 Correct 145 ms 38340 KB Output is correct
13 Correct 135 ms 42840 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1499 ms 51656 KB Output is correct
2 Execution timed out 3065 ms 52152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 415 ms 92280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 45888 KB Output is correct
2 Correct 157 ms 45808 KB Output is correct
3 Correct 149 ms 45892 KB Output is correct
4 Correct 154 ms 46020 KB Output is correct
5 Correct 136 ms 42704 KB Output is correct
6 Correct 13 ms 9676 KB Output is correct
7 Correct 14 ms 9596 KB Output is correct
8 Correct 13 ms 9560 KB Output is correct
9 Correct 154 ms 39840 KB Output is correct
10 Correct 152 ms 39748 KB Output is correct
11 Correct 151 ms 39716 KB Output is correct
12 Correct 145 ms 38340 KB Output is correct
13 Correct 135 ms 42840 KB Output is correct
14 Incorrect 12 ms 9164 KB Output isn't correct
15 Halted 0 ms 0 KB -