제출 #1275235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275235		choed	Sprinkler (JOI22_sprinkler)	C++20	0 / 100	497 ms	80628 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));
ll n, l;

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;
        if(parent[v]==0)
            parent[v]=u;
        else parent[u]=v;
    }
    
    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);
        }else{
            cin >> x;
            ll koef=query(x, 0);
            ans.push_back((koef*h[x])%l);
        }
    }

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

/*
g++ sigma.cpp -o a
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: 0 / 3
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17