Submission #1262355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262355		PlayVoltz	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	719 ms	98812 KiB

sprinkler

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

vector<int> par;
vector<vector<int> > graph;

void dfs(int node, int p){
	par[node]=p;
	for (auto num:graph[node])if (num!=p)dfs(num, node);
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, MOD, q, t, a, b, c;
	cin>>n>>MOD;
	par.resize(n+1);
	graph.resize(n+1);
	for (int i=1; i<n; ++i){
		cin>>a>>b;
		graph[a].pb(b);
		graph[b].pb(a);
	}
	dfs(1, 1);
	vector<int> vect(n+1);
	vector<vector<int> > mult(n+1, vector<int>(41, 1));
	for (int i=1; i<=n; ++i)cin>>vect[i];
	cin>>q;
	while (q--){
		cin>>t;
		if (t==1){
			cin>>a>>b>>c;
			for (int i=b; i>=0; --i){
				if (i&&a!=par[a])mult[a][i-1]=(mult[a][i-1]*c)%MOD;
				mult[a][i]=(mult[a][i]*c)%MOD;
				a=par[a];
			}
		}
		else{
			cin>>a;
			int res=vect[a];
			for (int i=0; i<=40; ++i){
				res=(res*mult[a][i])%MOD;
				if (a==par[a])break;
				a=par[a];
			}
			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