Submission #1206939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206939		AmirAli_H1	Sprinkler (JOI22_sprinkler)	C++20	12 / 100	697 ms	84256 KiB

sprinkler

// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 4;
const int maxd = 42;

int n, M, q;
vector<int> adj[maxn]; int par[maxn];
ll A[maxn][maxd]; vector<int> lsx;

void dfs(int v, int p = -1) {
	par[v] = p;
	for (int u : adj[v]) {
		if (u == p) continue;
		dfs(u, v);
	}
}

void setx(int v, int d, ll w) {
	lsx.clear(); lsx.pb(v);
	for (int T = 0; T < d; T++) {
		v = par[v];
		if (v != -1) lsx.pb(v);
		else break;
	}
	for (int j = len(lsx) - 1; j >= 0; j--) {
		int v = lsx[j];
		if (j == len(lsx) - 1) {
			for (int T = 0; T <= d - j; T++) (A[v][T] *= w) %= M;
		}
		else {
			(A[v][d - j - 1] *= w) %= M; (A[v][d - j] *= w) %= M;
		}
	}
}

int calx(int v) {
	int res = 1, j = 0;
	while (v != -1 && j < maxd) {
		(res *= A[v][j]) %= M;
		v = par[v]; j++;
	}
	return res;
}

void solve() {
	cin >> n >> M;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v; u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}
	for (int i = 0; i < n; i++) {
		cin >> A[i][0];
		for (int j = 1; j < maxd; j++) A[i][j] = 1;
	}
	dfs(0);
	cin >> q;
	while (q--) {
		int op;
		cin >> op;
		if (op == 1) {
			int x, d, w;
			cin >> x >> d >> w; x--;
			setx(x, d, w);
		}
		else {
			int x;
			cin >> x; x--;
			cout << calx(x) << endl;
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int T = 1;
	while (T--) {
		solve();
	}

	return 0;
}

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