oj.uz

Submission #558465

# Submission time Handle Problem Language Result Execution time Memory
558465 2022-05-07T12:14:24 Z savacska Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 126444 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXD = 40;
const int MAXN = 200000;
int MOD = 0;

vector <int> g[MAXN + 5];
int height[MAXN + 5], position[MAXN + 5], parent[MAXN + 5], start_height[MAXN + 5];
vector <int> rows[MAXN + 5];
pair <int, int> subtree[MAXD + 5][MAXN + 5];
vector <pair <int, int> > tree[MAXN + 5];

int binpow(int x, int step)
{
 	if (step == 0) return 1;
 	if (step % 2 == 0)
 	{
 	 	int t = binpow(x, step / 2);
 	 	return (ll) t * (ll) t % (ll) MOD;
 	}
 	else return (ll) x * (ll) binpow(x, step - 1) % (ll) MOD;
}

void dfs(int v, int pr, int hei)
{
	parent[v] = pr;
	height[v] = hei;
	position[v] = (int) rows[hei].size();
	rows[hei].pb(v);

	int pos = -1;
	for (int i = 0; i < (int) g[v].size(); i++)
		if (g[v][i] == pr) pos = i;
	if (pos != -1)
	{
	 	swap(g[v][pos], g[v].back());
	 	g[v].pop_back();
	}

	for (int u : g[v])
		dfs(u, v, hei + 1);

	subtree[0][v] = mp(position[v], position[v]);
	if (!g[v].empty())
	{
	 	subtree[1][v] = mp(position[g[v][0]], position[g[v].back()]);
	 	int lef = 0, rig = (int) g[v].size() - 1;
	 	for (int i = 2; i <= MAXD; i++)
	 	{
	 	 	while (lef <= rig && subtree[i - 1][g[v][lef]] == mp(-1, -1)) lef++;
	 	 	while (lef <= rig && subtree[i - 1][g[v][rig]] == mp(-1, -1)) rig--;
	 	 	if (lef <= rig) subtree[i][v] = mp(subtree[i - 1][g[v][lef]].x, subtree[i - 1][g[v][rig]].y);
	 	 	else break;
	 	}
	}
	return;
}

void build(vector <pair <int, int> > &tree, int v, int lef, int rig, const vector <int> &num)
{
 	if (lef == rig)
 	{
 		int vv = num[lef];
 		tree[v] = mp(start_height[vv], 1);
 		return; 	
 	}
 	int mid = (lef + rig) / 2;
 	build(tree, 2 * v, lef, mid, num);
 	build(tree, 2 * v + 1, mid + 1, rig, num);
 	tree[v] = mp((ll) tree[2 * v].x * (ll) tree[2 * v + 1].x % (ll) MOD, 1);
 	return;
}

void full(vector <pair <int, int> > &tree, int v, int lef, int rig, int mn)
{
	tree[v].y = (ll) tree[v].y * (ll) mn % (ll) MOD;
	tree[v].x = (ll) tree[v].x * (ll) binpow(mn, rig - lef + 1) % (ll) MOD;
	return;
}

void push(vector <pair <int, int> > &tree, int v, int lef, int rig)
{
 	int mid = (lef + rig) / 2;
 	full(tree, 2 * v, lef, mid, tree[v].y);
 	full(tree, 2 * v + 1, mid + 1, rig, tree[v].y);
 	tree[v].y = 1;
 	return;
}

int get_height(vector <pair <int, int> > &tree, int v, int lef, int rig, int pos)
{
 	if (lef == rig) return tree[v].x;
 	push(tree, v, lef, rig);
 	int mid = (lef + rig) / 2;
 	if (pos <= mid) return get_height(tree, 2 * v, lef, mid, pos);
 	else return get_height(tree, 2 * v + 1, mid + 1, rig, pos);
}

void update(vector <pair <int, int> > &tree, int v, int lef, int rig, int A, int B, int mn)
{
 	if (lef > B || rig < A) return;
 	if (A <= lef && rig <= B)
 	{
 	 	full(tree, v, lef, rig, mn);
 	 	return;
 	}
 	push(tree, v, lef, rig);
 	int mid = (lef + rig) / 2;
 	update(tree, 2 * v, lef, mid, A, B, mn);
 	update(tree, 2 * v + 1, mid + 1, rig, A, B, mn);
 	tree[v].x = (ll) tree[2 * v].x * (ll) tree[2 * v + 1].x % (ll) MOD;
 	return;
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	
 	int n, mod;
 	cin >> n >> mod;
 	MOD = mod;
 	
 	for (int i = 0; i <= MAXD; i++)
 		for (int j = 1; j <= n; j++)
 			subtree[i][j] = mp(-1, -1);

 	for (int i = 1; i < n; i++)
 	{
 	 	int u, v;
 	 	cin >> u >> v;
 	 	g[u].pb(v), g[v].pb(u);
 	}

 	for (int i = 1; i <= n; i++) cin >> start_height[i];

 	dfs(1, -1, 0);
 	
 	{
 	 	int h = 0;
 	 	while (!rows[h].empty())
 	 	{
 	 	 	int sz = (int) rows[h].size();
 	 	 	tree[h].resize(4 * sz, mp(0, 0));
 	 	 	build(tree[h], 1, 0, sz - 1, rows[h]);
 	 		h++;
 	 	}
 	}
 	
 	int quer;
 	cin >> quer;
 	
 	for (int rep = 1; rep <= quer; rep++)
 	{
 	 	int typ;
 	 	cin >> typ;
 	 	if (typ == 1)
 	 	{
 	 	 	int vert, dist, mn;
 	 	 	cin >> vert >> dist >> mn;

 	 	 	vector <int> path;
 	 	 	int tek = vert;
 	 	 	path.pb(tek);
 	 	 	for (int i = 1; i <= dist; i++)
 	 	 	{
 	 	 		if (parent[tek] == -1) break;
 	 	 		tek = parent[tek];
 	 	 		path.pb(tek);
 	 	 	}
 	 	 	for (int fin = height[vert] - dist; fin <= height[vert] + dist; fin++)
 	 	 	{
 	 	 	 	int x = (dist + height[vert] - fin) / 2;
 	 	 	 	if (x >= (int) path.size()) x = (int) path.size() - 1;
 	 	 	 	if (height[path[x]] > fin) continue;

 	 	 	 	int y = fin - height[path[x]];
 	 	 	 	pair <int, int> bounds = subtree[y][path[x]];
 	 	 	 	if (bounds.x == -1) continue;
 	 	 	 	update(tree[fin], 1, 0, (int) rows[fin].size() - 1, bounds.x, bounds.y, mn);
 	 	 	}
 	 	}
 	 	else
 	 	{
 	 		int vert;
 	 		cin >> vert;

 	 		cout << get_height(tree[height[vert]], 1, 0, (int) rows[height[vert]].size() - 1, position[vert]) << '\n';
 	 	}
 	}
 	return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14684 KB Output is correct
2 Correct 7 ms 14692 KB Output is correct
3 Correct 7 ms 14676 KB Output is correct
4 Correct 9 ms 15188 KB Output is correct
5 Correct 12 ms 15084 KB Output is correct
6 Correct 11 ms 15084 KB Output is correct
7 Correct 10 ms 15080 KB Output is correct
8 Correct 10 ms 15060 KB Output is correct
9 Correct 7 ms 14692 KB Output is correct
10 Correct 8 ms 14676 KB Output is correct
11 Correct 8 ms 14676 KB Output is correct
12 Correct 8 ms 14640 KB Output is correct
13 Correct 8 ms 14804 KB Output is correct
14 Correct 8 ms 14676 KB Output is correct
15 Correct 8 ms 14688 KB Output is correct
16 Correct 8 ms 14676 KB Output is correct
17 Correct 8 ms 14676 KB Output is correct
18 Correct 8 ms 14676 KB Output is correct
19 Correct 9 ms 14676 KB Output is correct
20 Correct 7 ms 14676 KB Output is correct
21 Correct 8 ms 14688 KB Output is correct
22 Correct 8 ms 14676 KB Output is correct
23 Correct 8 ms 14676 KB Output is correct
24 Correct 8 ms 14684 KB Output is correct
25 Correct 8 ms 14676 KB Output is correct
26 Correct 8 ms 14628 KB Output is correct
27 Correct 8 ms 14608 KB Output is correct
28 Correct 9 ms 14676 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 699 ms 99392 KB Output is correct
3 Correct 1457 ms 96180 KB Output is correct
4 Correct 572 ms 110608 KB Output is correct
5 Correct 950 ms 97720 KB Output is correct
6 Correct 1624 ms 97688 KB Output is correct
7 Correct 1731 ms 97840 KB Output is correct
8 Correct 1612 ms 98288 KB Output is correct
9 Correct 568 ms 119512 KB Output is correct
10 Correct 694 ms 114476 KB Output is correct
11 Correct 747 ms 99320 KB Output is correct
12 Correct 1343 ms 96292 KB Output is correct
13 Correct 853 ms 96616 KB Output is correct
14 Correct 3361 ms 96628 KB Output is correct
15 Correct 3936 ms 96828 KB Output is correct
16 Correct 3784 ms 102292 KB Output is correct
17 Correct 3794 ms 103536 KB Output is correct
18 Correct 8 ms 14676 KB Output is correct
19 Correct 8 ms 14680 KB Output is correct
20 Correct 10 ms 14676 KB Output is correct
21 Correct 10 ms 14740 KB Output is correct
22 Correct 9 ms 14676 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 699 ms 99392 KB Output is correct
3 Correct 1457 ms 96180 KB Output is correct
4 Correct 572 ms 110608 KB Output is correct
5 Correct 950 ms 97720 KB Output is correct
6 Correct 1624 ms 97688 KB Output is correct
7 Correct 1731 ms 97840 KB Output is correct
8 Correct 1612 ms 98288 KB Output is correct
9 Correct 568 ms 119512 KB Output is correct
10 Correct 694 ms 114476 KB Output is correct
11 Correct 747 ms 99320 KB Output is correct
12 Correct 1343 ms 96292 KB Output is correct
13 Correct 853 ms 96616 KB Output is correct
14 Correct 3361 ms 96628 KB Output is correct
15 Correct 3936 ms 96828 KB Output is correct
16 Correct 3784 ms 102292 KB Output is correct
17 Correct 3794 ms 103536 KB Output is correct
18 Correct 8 ms 14676 KB Output is correct
19 Correct 8 ms 14680 KB Output is correct
20 Correct 10 ms 14676 KB Output is correct
21 Correct 10 ms 14740 KB Output is correct
22 Correct 9 ms 14676 KB Output is correct
23 Correct 8 ms 14676 KB Output is correct
24 Correct 852 ms 107140 KB Output is correct
25 Correct 1896 ms 106560 KB Output is correct
26 Correct 643 ms 126444 KB Output is correct
27 Correct 1065 ms 106932 KB Output is correct
28 Correct 2000 ms 107252 KB Output is correct
29 Correct 2092 ms 106944 KB Output is correct
30 Correct 1935 ms 107308 KB Output is correct
31 Correct 588 ms 120344 KB Output is correct
32 Correct 793 ms 125136 KB Output is correct
33 Correct 814 ms 106960 KB Output is correct
34 Correct 2144 ms 107128 KB Output is correct
35 Correct 8 ms 14676 KB Output is correct
36 Correct 10 ms 14676 KB Output is correct
37 Correct 9 ms 14620 KB Output is correct
38 Correct 10 ms 14692 KB Output is correct
39 Correct 9 ms 14676 KB Output is correct
40 Correct 9 ms 14712 KB Output is correct
41 Correct 9 ms 14676 KB Output is correct
42 Correct 8 ms 14692 KB Output is correct
43 Correct 9 ms 14808 KB Output is correct
44 Correct 11 ms 14688 KB Output is correct
45 Correct 9 ms 14676 KB Output is correct
46 Correct 9 ms 14676 KB Output is correct
47 Correct 8 ms 14664 KB Output is correct
48 Correct 9 ms 14676 KB Output is correct
49 Correct 9 ms 14676 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 1002 ms 116732 KB Output is correct
3 Execution timed out 4091 ms 118148 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 1154 ms 112508 KB Output is correct
3 Execution timed out 4029 ms 113012 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14684 KB Output is correct
2 Correct 7 ms 14692 KB Output is correct
3 Correct 7 ms 14676 KB Output is correct
4 Correct 9 ms 15188 KB Output is correct
5 Correct 12 ms 15084 KB Output is correct
6 Correct 11 ms 15084 KB Output is correct
7 Correct 10 ms 15080 KB Output is correct
8 Correct 10 ms 15060 KB Output is correct
9 Correct 7 ms 14692 KB Output is correct
10 Correct 8 ms 14676 KB Output is correct
11 Correct 8 ms 14676 KB Output is correct
12 Correct 8 ms 14640 KB Output is correct
13 Correct 8 ms 14804 KB Output is correct
14 Correct 8 ms 14676 KB Output is correct
15 Correct 8 ms 14688 KB Output is correct
16 Correct 8 ms 14676 KB Output is correct
17 Correct 8 ms 14676 KB Output is correct
18 Correct 8 ms 14676 KB Output is correct
19 Correct 9 ms 14676 KB Output is correct
20 Correct 7 ms 14676 KB Output is correct
21 Correct 8 ms 14688 KB Output is correct
22 Correct 8 ms 14676 KB Output is correct
23 Correct 8 ms 14676 KB Output is correct
24 Correct 8 ms 14684 KB Output is correct
25 Correct 8 ms 14676 KB Output is correct
26 Correct 8 ms 14628 KB Output is correct
27 Correct 8 ms 14608 KB Output is correct
28 Correct 9 ms 14676 KB Output is correct
29 Correct 8 ms 14676 KB Output is correct
30 Correct 699 ms 99392 KB Output is correct
31 Correct 1457 ms 96180 KB Output is correct
32 Correct 572 ms 110608 KB Output is correct
33 Correct 950 ms 97720 KB Output is correct
34 Correct 1624 ms 97688 KB Output is correct
35 Correct 1731 ms 97840 KB Output is correct
36 Correct 1612 ms 98288 KB Output is correct
37 Correct 568 ms 119512 KB Output is correct
38 Correct 694 ms 114476 KB Output is correct
39 Correct 747 ms 99320 KB Output is correct
40 Correct 1343 ms 96292 KB Output is correct
41 Correct 853 ms 96616 KB Output is correct
42 Correct 3361 ms 96628 KB Output is correct
43 Correct 3936 ms 96828 KB Output is correct
44 Correct 3784 ms 102292 KB Output is correct
45 Correct 3794 ms 103536 KB Output is correct
46 Correct 8 ms 14676 KB Output is correct
47 Correct 8 ms 14680 KB Output is correct
48 Correct 10 ms 14676 KB Output is correct
49 Correct 10 ms 14740 KB Output is correct
50 Correct 9 ms 14676 KB Output is correct
51 Correct 8 ms 14676 KB Output is correct
52 Correct 852 ms 107140 KB Output is correct
53 Correct 1896 ms 106560 KB Output is correct
54 Correct 643 ms 126444 KB Output is correct
55 Correct 1065 ms 106932 KB Output is correct
56 Correct 2000 ms 107252 KB Output is correct
57 Correct 2092 ms 106944 KB Output is correct
58 Correct 1935 ms 107308 KB Output is correct
59 Correct 588 ms 120344 KB Output is correct
60 Correct 793 ms 125136 KB Output is correct
61 Correct 814 ms 106960 KB Output is correct
62 Correct 2144 ms 107128 KB Output is correct
63 Correct 8 ms 14676 KB Output is correct
64 Correct 10 ms 14676 KB Output is correct
65 Correct 9 ms 14620 KB Output is correct
66 Correct 10 ms 14692 KB Output is correct
67 Correct 9 ms 14676 KB Output is correct
68 Correct 9 ms 14712 KB Output is correct
69 Correct 9 ms 14676 KB Output is correct
70 Correct 8 ms 14692 KB Output is correct
71 Correct 9 ms 14808 KB Output is correct
72 Correct 11 ms 14688 KB Output is correct
73 Correct 9 ms 14676 KB Output is correct
74 Correct 9 ms 14676 KB Output is correct
75 Correct 8 ms 14664 KB Output is correct
76 Correct 9 ms 14676 KB Output is correct
77 Correct 9 ms 14676 KB Output is correct
78 Correct 8 ms 14676 KB Output is correct
79 Correct 1002 ms 116732 KB Output is correct
80 Execution timed out 4091 ms 118148 KB Time limit exceeded
81 Halted 0 ms 0 KB -