Submission #1274954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274954		raditya_noor	Sprinkler (JOI22_sprinkler)	C++20	0 / 100	4097 ms	81420 KiB

sprinkler

#include <bits/stdc++.h>
#define fr first
#define sc second
#define psb push_back
#define ppb pop_back
#define ps push
#define pp pop
#define sz size
#define em empty
#define tp top
#define ft front
#define ll long long
using namespace std;

int main(){
	//input graph n shi
	int n; ll l; cin >> n >> l;
	vector <int> graph[n + 1];
	for(int i = 1, u, v; i <= n - 1; i++){
		cin >> u >> v;
		graph[u].psb(v); graph[v].psb(u);
	}
	ll h[n + 1]; for(int i = 1; i <= n; i++) cin >> h[i];
	
	//set multiplier
	ll mul[n + 1][41]; for(int i = 1; i <= n; i++) for(int j = 0; j <= 40; j++) mul[i][j] = 1;
	//set roots
	int root[n + 1] = {0}; 
	queue <pair <int, int>> qu; for(int i = 0; i < graph[1].sz(); i++) qu.ps({graph[1][i], 1});
	while(!qu.em()){
		int p = qu.ft().sc, c = qu.ft().fr;
		root[c] = p;
		for(int i = 0; i < graph[c].sz(); i++){
			if(graph[c][i] != p){
				qu.ps({graph[c][i], c});
			}
		}
		qu.pp();
	}
	//process shit
	int q; cin >> q;
	while(q--){
		int t; cin >> t;
		if(t == 1){
			int x, d; ll w; cin >> x >> d >> w;
			//go root
			h[x] *= w;
			h[x] %= l;
			while(d > 0 && x != root[x]){
				mul[x][d] *= w;
//				mul[x][d - 1] *= w;
				d--;
				h[root[x]] *= w;
				x = root[x];
			}
		}else if(t == 2){
			int x, d = 1; cin >> x; ll tot = h[x];
			x = root[x];
			//go root
			while(x != root[x]){
				tot *= mul[x][d];
				tot %= l;
				x = root[x];
				d++;
			}
//			cout << '>';
			cout << tot % l << endl;
		}
	}
}

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