Submission #1125704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125704		Icelast	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	2851 ms	92664 KiB

sprinkler

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void solve(){
    ll n, L, Q;
    cin >> n >> L;
    ll mod = L;
    vector<vector<int>> adj(n+1);
    vector<ll> a(n+1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    vector<int> pa(n+1, 0);
    auto dfs = [&](auto dfs, int u, int p) -> void{
        pa[u] = p;
        for(int v : adj[u]){
            if(v == p) continue;
            dfs(dfs, v, u);
        }
    };
    dfs(dfs, 1, 0);
    cin >> Q;
    vector<vector<ll>> lazy(n+1, vector<ll>(41, 1));
    for(int it = 1; it <= Q; it++){
        ll t, x, d, w;
        cin >> t;
        if(t == 1){
            cin >> x >> d >> w;
            for(int i = 0; i <= d; i++){
                if(x == 1){
                    for(int j = 0; j <= d-i; j++){
                        lazy[x][j] *= w;
                        lazy[x][j] %= mod;
                    }
                    break;
                }
                lazy[x][d-i] *= w;
                lazy[x][d-i] %= mod;
                if(d-i-1 >= 0){
                    lazy[x][d-i-1] *= w;
                    lazy[x][d-i-1] %= mod;
                }
                x = pa[x];
            }
        }else{
            cin >> x;
            ll res = a[x];
            for(int i = 0; i <= 40; i++){
                if(x == 0) break;
                res *= lazy[x][i];
                res %= mod;
                x = pa[x];
            }
            cout << res << "\n";
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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