Submission #709932

#	Time	Username	Problem	Language	Result	Execution time	Memory
709932		urosk	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	1068 ms	100548 KiB

sprinkler

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
//using namespace __gnu_pbds;
ll mod;
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}

#define maxn 200005
#define maxd 45
ll n,q;
vector<ll> g[maxn];
ll dp[maxn][maxd];
ll par[maxn];
void dfs(ll u,ll p){
    par[u] = p;
    for(ll s : g[u]){
        if(s==p) continue;
        dfs(s,u);
    }
}
void tc(){
    cin >> n >> mod;
    for(ll i = 1;i<=n-1;i++){
        ll x,y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    for(ll i = 1;i<=n;i++) for(ll j = 0;j<maxd;j++) dp[i][j] = 1;
    for(ll i = 1;i<=n;i++) cin >> dp[i][0];
    dfs(1,1);
    cin >> q;
    while(q--){
        ll tip; cin >> tip;
        if(tip==1){
            ll x,y,d;
            cin >> x >> d >> y;
            while(1){
                dp[x][d] = mul(dp[x][d],y);
                if(!d) break;
                d--;
                dp[x][d] = mul(dp[x][d],y);
                if(x!=1) x = par[x];
                else{
                    if(!d) break;
                    d--;
                }
            }
        }else{
            ll x;
            cin >> x;
            ll ans = 1;
            for(ll i = 0;i<maxd;i++){
                ans = mul(ans,dp[x][i]);
                if(x==1) break;
                x = par[x];
            }
            cout<<ans<<endl;
        }
    }
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}

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