Submission #1146836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146836		mariaclara	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	798 ms	86212 KiB

sprinkler

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")

using namespace std;

typedef long long ll;
typedef pair<ll,int> pii;
const int MAXN = 2e5+5;
int MOD;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, q, h[MAXN], pai[MAXN];
ll dist[45][MAXN];
vector<int> edges[MAXN];

void dfs(int x) {
    for(int viz : edges[x])
        if(viz != pai[x]) pai[viz] = x, dfs(viz);
}

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

    cin >> n >> MOD;

    for(int i = 1, a, b; i < n; i++) {
        cin >> a >> b;
        edges[a].pb(b);
        edges[b].pb(a);
    }

    for(int i = 1; i <= n; i++) cin >> h[i];

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= 40; j++) dist[j][i] = 1;

    cin >> q;

    dfs(1);

    while(q--) {
        int tipo, id, d, w;
        cin >> tipo;

        if(tipo == 1) {
            cin >> id >> d >> w;

            for(int i = 0; i <= d and id != 0; id = pai[id], i++) {
                dist[d - i][id] = (dist[d - i][id] * w)%MOD;
                if(i != d) dist[d - i - 1][id] = (dist[d - i - 1][id] * w)%MOD;
                if(id != 1) continue;

                for(int it = d - i - 2; it >= 0; it--) dist[it][id] = (dist[it][id] * w)%MOD;
            }
        } 
        else {
            cin >> id;
            ll ans = h[id];

            for(int i = 0, anc = id; i <= 40 and anc != 0; anc = pai[anc], i++)
                ans = (ans * dist[i][anc])%MOD;

            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