Submission #1050798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050798		0npata	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1412 ms	106672 KiB

sprinkler

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

#define int long long
#define vec vector
#define arr array

const int MXN = 200'005;
const int MXD = 43;

int pars[MXN];
vec<int> tree[MXN];

void dfs0(int u = 0, int p = -1) {
	pars[u] = p;
	for(int v : tree[u]) {
		if(v == p) continue;
		dfs0(v, u);
	}
}

int32_t main() {
	int N, L;
	cin >> N >> L;
	for(int i = 0; i<N-1; i++) {
		int u, v;
		cin >> u >> v;
		u--,v--;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	dfs0();
	vec<vec<int>> contr(N, vec<int>(MXD+1, 1));

	for(int i = 0; i<N; i++) {
		int h;
		cin >> h;
		contr[i][0] = h;
	}

	int Q;
	cin >> Q;
	while(Q--) {
		int t, u;
		cin >> t >> u;
		u--;
		if(t==1) {
			int d, m;
			cin >> d >> m;
			while(u != -1 && d >= 0) {
				//cerr <<"UPD: " <<  u << '\n';
				contr[u][d] *= m;
				contr[u][d] %= L;
				u = pars[u];
				d--;
			}
			//cerr <<"----------" << '\n';
			if(false){
			for(int i = 0; i<N; i++) {
				for(int j = 0; j<5; j++) {
					cerr << contr[i][j] << ' ';
				}
				cerr << '\n';
			}
			cerr << '\n';
			}
			//cerr << "------------------" << '\n';
		}
		else {
			assert(t==2);
			int res = 1;
			for(int i = 0; i<MXD && u != -1; i++) {
				for(int j = i; j<((pars[u] == -1) ? (MXD+1) : (i+2)); j++) {
					res *= contr[u][j];
					res %= L;
					//cerr << "MUL: " << res << '\n';
				}
				u = pars[u];
			}
			cout << res << '\n';
		}
	}
}

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