Submission #1274534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274534		neisenn	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	764 ms	96640 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli; 
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
typedef tuple<ll, int, int> tii;
const char nl = '\n';
const int mod = 998244353;
const ll INF = 1e18;
const int inf = 1e9;
vector<vector<int>> adj;
vector<int> par;

void dfs(int cur, int p){
    for (int ch : adj[cur]){
        if (ch == p) continue;
        dfs(ch, cur);
        par[ch] = cur;
    }
}

void solve(){
    int n, l; 
    cin >> n >> l;
    adj.resize(n+1);
    par.resize(n+1, -1);
    for (int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    ll h[n+1];
    for (int i = 1; i <= n; i++){
        cin >> h[i];
    }
    dfs(1, -1);
    int q; cin >> q;
    vector<vector<ll>> dp(n+1, vector<ll> (41, 1));
    // dp[i][j] = update yang tersimpan di node i dari anak anaknya dengan jarak masih bisa jalan j
    while (q--){
        int id; cin >> id;
        if (id == 1){
            int x, d; ll k;
            cin >> x >> d >> k;
            int cur = x;
            for (int i = d; i >= 0; i--){
                // cout << "UPDATE " << cur << ' ' << i << ' ' << k << nl;
                dp[cur][i] *= k;
                dp[cur][i] %= l;
                cur = par[cur];
                if (cur == -1) break;
            }
        }
        else {
            int x; cin >> x;
            ll ans = h[x];
            int cur = x;
            int st = 0;
            for (int i = 0; i <= 40; i++){
                if (cur == 1){
                    for (int j = i; j <= 40; j++){
                        // if (dp[cur][j] > 1) cout << "ada " << cur << ' ' << j << ' ' << dp[cur][j] << nl;
                        ans *= dp[cur][j];
                        ans %= l;
                    }
                    break;
                }
                // if (dp[cur][i] > 1) cout << "ada " << cur << ' ' << i << nl;
                // cout << dp[cur][i] << ' ';
                ans *= dp[cur][i];
                ans %= l;
                if (i+1 <= 40){
                    ans *= dp[cur][i+1]; 
                    ans %= l;
                }
                cur = par[cur];
                if (cur == -1) break;
            }
            cout << ans << nl;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1; // cin >> t;
    while (t--){
        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