oj.uz

Submission #558463

# Submission time Handle Problem Language Result Execution time Memory
558463 2022-05-07T12:06:09 Z savacska Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 127200 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 = g[v][0], rig = g[v].back();
	 	for (int i = 2; i <= MAXD; i++)
	 	{
	 	 	while (lef <= rig && subtree[i - 1][lef] == mp(-1, -1)) lef++;
	 	 	while (lef <= rig && subtree[i - 1][rig] == mp(-1, -1)) rig--;
	 	 	if (lef <= rig) subtree[i][v] = mp(subtree[i - 1][lef].x, subtree[i - 1][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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14676 KB Output is correct
2 Correct 8 ms 14676 KB Output is correct
3 Correct 10 ms 14712 KB Output is correct
4 Correct 13 ms 15204 KB Output is correct
5 Incorrect 10 ms 15060 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14632 KB Output is correct
2 Correct 722 ms 107168 KB Output is correct
3 Correct 1482 ms 106972 KB Output is correct
4 Correct 616 ms 119516 KB Output is correct
5 Correct 932 ms 106924 KB Output is correct
6 Correct 1696 ms 104560 KB Output is correct
7 Correct 1759 ms 106672 KB Output is correct
8 Correct 1605 ms 105104 KB Output is correct
9 Correct 633 ms 127200 KB Output is correct
10 Correct 674 ms 125172 KB Output is correct
11 Correct 759 ms 105428 KB Output is correct
12 Correct 1424 ms 104032 KB Output is correct
13 Correct 863 ms 107868 KB Output is correct
14 Correct 3333 ms 108024 KB Output is correct
15 Execution timed out 4006 ms 97932 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14632 KB Output is correct
2 Correct 722 ms 107168 KB Output is correct
3 Correct 1482 ms 106972 KB Output is correct
4 Correct 616 ms 119516 KB Output is correct
5 Correct 932 ms 106924 KB Output is correct
6 Correct 1696 ms 104560 KB Output is correct
7 Correct 1759 ms 106672 KB Output is correct
8 Correct 1605 ms 105104 KB Output is correct
9 Correct 633 ms 127200 KB Output is correct
10 Correct 674 ms 125172 KB Output is correct
11 Correct 759 ms 105428 KB Output is correct
12 Correct 1424 ms 104032 KB Output is correct
13 Correct 863 ms 107868 KB Output is correct
14 Correct 3333 ms 108024 KB Output is correct
15 Execution timed out 4006 ms 97932 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Incorrect 987 ms 123152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14676 KB Output is correct
2 Incorrect 1158 ms 118656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14676 KB Output is correct
2 Correct 8 ms 14676 KB Output is correct
3 Correct 10 ms 14712 KB Output is correct
4 Correct 13 ms 15204 KB Output is correct
5 Incorrect 10 ms 15060 KB Output isn't correct
6 Halted 0 ms 0 KB -