Submission #1153352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153352		Dan4Life	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	635 ms	85720 KiB

sprinkler

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;

const int mxN = (int)2e5+100;
const int INF = (int)1e9;
const ll LINF = (ll)2e18;
int MOD = (int)1e9+7;

int n, q;
vi adj[mxN];
int c[42][mxN];
int p[mxN];

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

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> MOD; adj[n+1].pb(1);
    for(int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        adj[a].pb(b), adj[b].pb(a);
    }
	for(int j = 0; j <= 40; j++)
		for(int i = 0; i <= n+40; i++) 
				c[j][i]=1;
    for(int i = 1; i <= n; i++) cin >> c[0][i];
    for(int i = n+2; i <= n+40; i++) adj[i].pb(i-1);
    dfs(n+40,0);
    cin >> q;
    while(q--){
        int t; cin >> t;
        if(t==1){
            int s, d, w; cin >> s >> d >> w;
            for(int dis = d-1; dis >= 0; dis--, s=p[s])
                for(int j : {0,1}) c[dis+j][s]*=w, c[dis+j][s]%=MOD;
            c[0][s]*=w, c[0][s]%=MOD;
        }
        else{
            int s, ans = 1; cin >> s;
            for(int d = 0; d <= 40; d++)
                ans*=c[d][s], ans%=MOD, s=p[s];
            cout << ans << "\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