oj.uz

Submission #999107

# Submission time Handle Problem Language Result Execution time Memory
999107 2024-06-15T06:47:41 Z vjudge1 Sumtree (INOI20_sumtree) C++17
50 / 100
 3000 ms 160336 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MXN = 1e6 + 5;
const int LOG = 20;
const int mod = 1e9 + 7;

struct FindUp
{
	int sz;
	vector<int> st;
	void init(int n)
	{
		sz = n;
		st.assign((n + 1) << 2, 0);
	}
	void add(int l, int r, int x, int lx, int rx, int val)
	{
		if (l > rx || r < lx) return;
		if (l >= lx && r <= rx)
		{
			st[x] += val;
			return;
		}
		int mid = (l + r) >> 1;
		add(l, mid, 2*x, lx, rx, val);
		add(mid + 1, r, 2*x + 1, lx, rx, val);
	}
	int get(int l, int r, int x, int ind)
	{
		if (l == r) return st[x];
		int mid = (l + r) >> 1;
		if (ind <= mid) return st[x] + get(l, mid, 2*x, ind);
		else return st[x] + get(mid + 1, r, 2*x + 1, ind);
	}
};
struct FindVAL
{
	int sz;
	vector<int> st;
	void init(int n)
	{
		sz = n;
		st.assign((n + 1) << 2, 0);
	}
	void add(int l, int r, int x, int ind, int val)
	{
		if (l == r)
		{
			st[x] += val;
			return;
		}
		int mid = (l + r) >> 1;
		if (ind <= mid) add(l, mid, 2*x, ind, val);
		else add(mid + 1, r, 2*x + 1, ind, val);
		st[x] = st[2*x] + st[2*x + 1];
	}
	int get(int l, int r, int x, int lx, int rx)
	{
		if (l > rx || r < lx) return 0;
		if (l >= lx && r <= rx) return st[x];
		int mid = (l + r) >> 1;
		return get(l, mid, 2*x, lx, rx) + get(mid + 1, r, 2*x + 1, lx, rx);
	}
};

int n, r;
vector<int> adj[MXN];
int f[MXN], tag[MXN];
int p[LOG][MXN], sz[MXN];
int in[MXN], out[MXN], tim;
FindUp stup;
FindVAL stsz, sts;
int res = 1, z = 0;

int pw(int a, int b, int c)
{
	a %= c;
	int res = 1;
	while (b)
	{
		if (b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}

int nck(int n, int k)
{
	if (min(n, k) < 0 || k > n) return 0;
	return (f[n] * pw((f[n - k] * f[k]) % mod, mod - 2, mod)) % mod;
}

void dfs(int a)
{
	sz[a] = 1;
	in[a] = ++tim;
	for (int &v : adj[a])
	{
		if (v == p[0][a]) continue;
		p[0][v] = a;
		dfs(v);
		sz[a] += sz[v];
 	}
	out[a] = tim;
}

int getco(int u)
{
	// cout << u << ' ' << sz[u] << ' ' << stsz.get(1, n, 1, in[u] + 1, out[u]) << ' ' << tag[u] << ' ' << sts.get(1, n, 1, in[u] + 1, out[u]) << '\n';
	return nck(sz[u] - stsz.get(1, n, 1, in[u] + 1, out[u]) - 1 + tag[u] - sts.get(1, n, 1, in[u] + 1, out[u]), tag[u] - sts.get(1, n, 1, in[u] + 1, out[u]));
}

int invalid(int u)
{
	return (sts.get(1, n, 1, in[u] + 1, out[u]) > tag[u]);
}

int UP(int u)
{
	u = p[0][u];
	while (tag[u] == -1) u = p[0][u];
	return u;
	int x = stup.get(1, n, 1, in[u]);
	for (int i = LOG - 1; i >= 0; i--)
	{
		if (stup.get(1, n, 1, in[p[i][u]]) == x) u = p[i][u];
	}
	return p[0][u];
}


signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	f[0] = 1;
	for (int i = 1; i < MXN; i++) 
	{
		f[i] = (f[i - 1] * i) % mod;
		tag[i] = -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);
	}
	int q;
	cin >> q;
	tag[1] = r;
	p[0][1] = 1;
	dfs(1);
	for (int i = 1; i < LOG; i++) for (int j = 1; j <= n; j++) p[i][j] = p[i - 1][p[i - 1][j]];
	stup.init(n), stsz.init(n), sts.init(n);
	stup.add(1, n, 1, 1, n, 1);
	stsz.add(1, n, 1, in[1], 1);
	res = getco(1);
	cout << res << '\n';
	while (q--)
	{
		int t;
		cin >> t;
		if (t == 1)
		{
			int u, v;
			cin >> u >> v;
			int P = UP(u);
			int S = stsz.get(1, n, 1, in[u] + 1, out[u]);
			tag[u] = v;
			int ff = invalid(P);
			if (!ff) res = (res * pw(getco(P), mod - 2, mod)) % mod;
			else z--;
			stsz.add(1, n, 1, in[u], -S + sz[u]);
			stsz.add(1, n, 1, in[P], S - sz[u]);
			
			S = sts.get(1, n, 1, in[u] + 1, out[u]);
			sts.add(1, n, 1, in[u], -S + tag[u]);
			sts.add(1, n, 1, in[P], S - tag[u]);
			ff = invalid(P);
			if (!ff) res = (res * getco(P)) % mod;
			else z++;
			ff = invalid(u);
			if (!ff) res = (res * getco(u)) % mod;
			else z++;

			stup.add(1, n, 1, in[u], out[u], 1);
		}
		else
		{
			int u;
			cin >> u;
			int P = UP(u);
			int S = stsz.get(1, n, 1, in[u] + 1, out[u]);
			int ff = invalid(P);
			if (!ff) res = (res * pw(getco(P), mod - 2, mod)) % mod;
			else z--;
			ff = invalid(u);
			if (!ff) res = (res * pw(getco(u), mod - 2, mod)) % mod;
			else z--;
			stsz.add(1, n, 1, in[u], S - sz[u]);
			stsz.add(1, n, 1, in[P], -S + sz[u]);

			S = sts.get(1, n, 1, in[u] + 1, out[u]);
			sts.add(1, n, 1, in[u], S - tag[u]);
			sts.add(1, n, 1, in[P], -S + tag[u]);
			ff = invalid(P);
			if (!ff) res = (res * getco(P)) % mod;
			else z++;

			stup.add(1, n, 1, in[u], out[u], -1);
			tag[u] = -1;
		}
		if (z) cout << 0 << '\n';
		else cout << res << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 153940 KB Output is correct
2 Correct 90 ms 153936 KB Output is correct
3 Correct 85 ms 153936 KB Output is correct
4 Correct 96 ms 153944 KB Output is correct
5 Correct 81 ms 150352 KB Output is correct
6 Correct 16 ms 88668 KB Output is correct
7 Correct 15 ms 88432 KB Output is correct
8 Correct 16 ms 88520 KB Output is correct
9 Correct 78 ms 149280 KB Output is correct
10 Correct 81 ms 149140 KB Output is correct
11 Correct 83 ms 149252 KB Output is correct
12 Correct 81 ms 146000 KB Output is correct
13 Correct 78 ms 149072 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 85848 KB Output is correct
2 Correct 14 ms 85848 KB Output is correct
3 Correct 15 ms 85852 KB Output is correct
4 Correct 15 ms 86072 KB Output is correct
5 Correct 16 ms 86108 KB Output is correct
6 Correct 18 ms 86416 KB Output is correct
7 Correct 19 ms 86364 KB Output is correct
8 Correct 19 ms 86360 KB Output is correct
9 Correct 21 ms 88412 KB Output is correct
10 Correct 21 ms 88508 KB Output is correct
11 Correct 23 ms 88668 KB Output is correct
12 Correct 16 ms 88412 KB Output is correct
13 Correct 23 ms 88548 KB Output is correct
14 Correct 23 ms 88412 KB Output is correct
15 Correct 23 ms 88668 KB Output is correct
16 Correct 21 ms 88412 KB Output is correct
17 Correct 22 ms 88624 KB Output is correct
18 Correct 20 ms 86228 KB Output is correct
19 Correct 23 ms 88412 KB Output is correct
20 Correct 18 ms 86364 KB Output is correct
21 Correct 18 ms 86176 KB Output is correct
22 Correct 15 ms 86108 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 153428 KB Output is correct
2 Correct 166 ms 156564 KB Output is correct
3 Correct 128 ms 156496 KB Output is correct
4 Correct 214 ms 157268 KB Output is correct
5 Correct 334 ms 155448 KB Output is correct
6 Correct 17 ms 88664 KB Output is correct
7 Correct 17 ms 88408 KB Output is correct
8 Correct 19 ms 88412 KB Output is correct
9 Correct 323 ms 153856 KB Output is correct
10 Correct 280 ms 153260 KB Output is correct
11 Correct 258 ms 153204 KB Output is correct
12 Correct 265 ms 153168 KB Output is correct
13 Execution timed out 3040 ms 160336 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 152292 KB Output is correct
2 Correct 582 ms 155724 KB Output is correct
3 Correct 554 ms 155732 KB Output is correct
4 Correct 589 ms 155684 KB Output is correct
5 Correct 600 ms 152212 KB Output is correct
6 Correct 575 ms 155732 KB Output is correct
7 Correct 544 ms 124668 KB Output is correct
8 Correct 545 ms 124824 KB Output is correct
9 Correct 595 ms 155724 KB Output is correct
10 Correct 570 ms 155984 KB Output is correct
11 Correct 563 ms 156012 KB Output is correct
12 Correct 481 ms 125012 KB Output is correct
13 Correct 267 ms 123476 KB Output is correct
14 Correct 362 ms 123476 KB Output is correct
15 Correct 370 ms 123428 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 153940 KB Output is correct
2 Correct 90 ms 153936 KB Output is correct
3 Correct 85 ms 153936 KB Output is correct
4 Correct 96 ms 153944 KB Output is correct
5 Correct 81 ms 150352 KB Output is correct
6 Correct 16 ms 88668 KB Output is correct
7 Correct 15 ms 88432 KB Output is correct
8 Correct 16 ms 88520 KB Output is correct
9 Correct 78 ms 149280 KB Output is correct
10 Correct 81 ms 149140 KB Output is correct
11 Correct 83 ms 149252 KB Output is correct
12 Correct 81 ms 146000 KB Output is correct
13 Correct 78 ms 149072 KB Output is correct
14 Correct 15 ms 85848 KB Output is correct
15 Correct 14 ms 85848 KB Output is correct
16 Correct 15 ms 85852 KB Output is correct
17 Correct 15 ms 86072 KB Output is correct
18 Correct 16 ms 86108 KB Output is correct
19 Correct 18 ms 86416 KB Output is correct
20 Correct 19 ms 86364 KB Output is correct
21 Correct 19 ms 86360 KB Output is correct
22 Correct 21 ms 88412 KB Output is correct
23 Correct 21 ms 88508 KB Output is correct
24 Correct 23 ms 88668 KB Output is correct
25 Correct 16 ms 88412 KB Output is correct
26 Correct 23 ms 88548 KB Output is correct
27 Correct 23 ms 88412 KB Output is correct
28 Correct 23 ms 88668 KB Output is correct
29 Correct 21 ms 88412 KB Output is correct
30 Correct 22 ms 88624 KB Output is correct
31 Correct 20 ms 86228 KB Output is correct
32 Correct 23 ms 88412 KB Output is correct
33 Correct 18 ms 86364 KB Output is correct
34 Correct 18 ms 86176 KB Output is correct
35 Correct 15 ms 86108 KB Output is correct
36 Correct 114 ms 153428 KB Output is correct
37 Correct 166 ms 156564 KB Output is correct
38 Correct 128 ms 156496 KB Output is correct
39 Correct 214 ms 157268 KB Output is correct
40 Correct 334 ms 155448 KB Output is correct
41 Correct 17 ms 88664 KB Output is correct
42 Correct 17 ms 88408 KB Output is correct
43 Correct 19 ms 88412 KB Output is correct
44 Correct 323 ms 153856 KB Output is correct
45 Correct 280 ms 153260 KB Output is correct
46 Correct 258 ms 153204 KB Output is correct
47 Correct 265 ms 153168 KB Output is correct
48 Execution timed out 3040 ms 160336 KB Time limit exceeded
49 Halted 0 ms 0 KB -