Submission #1275478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275478		choed	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	1032 ms	100568 KiB

sprinkler

#include <bits/stdc++.h>
#define GO_BEYOND ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define fi first
#define se second
#define pll pair<ll, ll>
#define plll pair<ll,pll>
using namespace std;

const ll MAXN=2e5;
vector<ll> h(MAXN+1);
vector<ll> parent(MAXN+1, 0LL); // kita bikin tree aja
vector<vector<ll>> anu(MAXN+1, vector<ll>(41LL, 1LL));
vector<bool> vis(MAXN+1, 0);
vector<ll> edge[MAXN+5];
ll n, l;

void maketree(ll x, ll par){
    vis[x]=1;
    parent[x]=par;
    for(auto u: edge[x]){
        if(!vis[u])
            maketree(u, x);
    }
}

void update(ll x, ll d, ll w){
    anu[x][d]=(anu[x][d]*w)%l;
    if(d<=0) return;
    // pastikan childnya yang dist odd bisa berpotongan dengannya
    if(x!=0) anu[x][d-1]=(anu[x][d-1]*w)%l;
    // cout << x << ' ' << d << ' ' << anu[x][d] << " UPDET" << endl;
    update(parent[x], d-1, w);
}

ll query(ll x, ll d){
    if(d>40) return 1;
    if(x==0) return anu[x][d];
    // cout << x << ' ' << d << ' ' << anu[x][d] << " HMZ" << endl;
    ll ret=(anu[x][d]*query(parent[x], d+1))%l;
    return ret;
}

void solve(){
    cin >> n >> l;
    ll u, v;
    for(int i=1; i<n; i++){
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    maketree(1, 0);
    
    for(int i=1; i<=n; i++)
        cin >> h[i];

    ll q; cin >> q;
    ll x, d, w, t;
    vector<ll> ans;
    while(q--){
        cin >> t;
        if(t==1){
            cin >> x >> d >> w;
            update(x, d, w);
            // cout << "WOW" << endl;
        }else{
            cin >> x;
            ll koef=query(x, 0);
            // cout << koef << " HUH" << endl;
            ans.push_back((koef*h[x])%l);
        }
    }

    for(auto x: ans)
        cout << x << endl;
}

/*
g++ sigma.cpp -o a
2 5
1 2
3
1
2
1 1 0 4
2 1

4 7
1 2
2 3
3 4
1
1
1
1
11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4

6 10
5 6
1 2
1 4
2 6
3 6
9
2
3
4
9
1
10
1 5 1 7
2 4
1 4 1 9
1 5 0 7
2 1
1 1 1 3
1 6 1 4
2 5
2 4
2 3
*/

int main(){
    GO_BEYOND;
    ll 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