Submission #544538

#	Time	Username	Problem	Language	Result	Execution time	Memory
544538		Jarif_Rahman	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	897 ms	52064 KiB

sprinkler

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int maxn = 200000;

vector<int> v[maxn];
int p[maxn];
int ml[maxn][41];

inline void dfs(int nd, int ss){
    p[nd] = ss;
    for(int x: v[nd]) if(x != ss) dfs(x, nd);
}

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

    int n, md; cin >> n >> md;

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

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

    for(int i = 0; i < n; i++) cin >> ml[i][0];
    dfs(0, -1);

    int q; cin >> q;
    while(q--){
        int tt; cin >> tt;

        if(tt == 1){
            int nd, d, w; cin >> nd >> d >> w; nd--;
            while(d >= 0){
                ml[nd][d]=(ll(ml[nd][d])*w)%md;
                if(d != 0) ml[nd][d-1]=(ll(ml[nd][d-1])*w)%md;
                if(p[nd] == -1){
                    for(int i = 0; i < d-1; i++) ml[nd][i]=(ll(ml[nd][i])*w)%md;
                    break;
                }
                d--;
                nd = p[nd];
            }
        }

        else{
            int nd; cin >> nd; nd--;
            int d = 0;

            int ans = 1;

            while(d <= 40){
                ans=(ll(ans)*ml[nd][d])%md;
                nd = p[nd];
                d++;
                if(nd == -1) break;
            }

            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