제출 #558491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558491		savacska	Sprinkler (JOI22_sprinkler)	C++17	41 / 100	4054 ms	94744 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], rows[MAXN + 5];
pair <int, int> subtree[MAXD + 5][MAXN + 5];
int tree[4 * MAXN + 5];
int path[MAXN + 5], start[MAXN + 5];

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

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

	return;
}

void dfsik(int v)
{
    for (int u : g[v])
    {
    	dfsik(u);
    }

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

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;
 	 	int sum = 0;
 	 	while (rows[h] > 0)
 	 	{
 	 	 	start[h] = sum;
 	 	 	sum += rows[h];
 	 	 	h++;
 	 	}
 	}
 	for (int i = 1; i <= n; i++) position[i] += start[height[i]];
 
	dfsik(1);
 	
 	int STEP = 1;
 	while (STEP < n) STEP *= 2;
 	for (int i = 1; i <= 2 * STEP - 1; i++) tree[i] = 1;

 	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;

 	 	 	 	int L = bounds.x + STEP, R = bounds.y + STEP;
 	 	 	 	while (L <= R)
				{
					if (L % 2 == 1)
					{
						tree[L] = (ll) tree[L] * (ll) mn % (ll) MOD;
						L++;
					}
					if (R % 2 == 0)
					{
					 	tree[R] = (ll) tree[R] * (ll) mn % (ll) MOD;
					 	R--;
				 	}
				 	L /= 2, R /= 2;
				}
 	 	 	}
 	 	}
 	 	else
 	 	{
 	 		int vert;
 	 		cin >> vert;

 	 		int pos = position[vert] + STEP;
 	 		int ans = start_height[vert];
 	 		while (pos > 0)
 	 		{
 	 		 	ans = (ll) ans * (ll) tree[pos] % (ll) MOD;
 	 		 	pos /= 2;
 	 		}
 	 		cout << ans << '\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