제출 #558470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558470		savacska	Sprinkler (JOI22_sprinkler)	C++17	41 / 100	4074 ms	126400 KiB

sprinkler

#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 path[MAXN + 5];

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;
}

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

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)
 	{
 	 	tree[v].y = (ll) tree[v].y * (ll) mn % (ll) MOD;
 	 	return;
 	}
 	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);
 	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;

 	 	 	int tek = vert;
 	 	 	int uk = 0;
 	 	 	path[uk] = tek;
 	 	 	uk++;
 	 	 	for (int i = 1; i <= dist; i++)
 	 	 	{
 	 	 		if (parent[tek] == -1) break;
 	 	 		tek = parent[tek];
 	 	 		path[uk] = tek;
 	 	 		uk++;
 	 	 	}
 	 	 	for (int fin = height[vert] - dist; fin <= height[vert] + dist; fin++)
 	 	 	{
 	 	 	 	int x = (dist + height[vert] - fin) / 2;
 	 	 	 	if (x >= uk) x = uk - 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], 1) << '\n';
 	 	}
 	}
 	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17