Submission #799571

#	Time	Username	Problem	Language	Result	Execution time	Memory
799571		eltu0815	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	807 ms	165328 KiB

sprinkler

#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
 
using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
 
ll n, m, k, q, l, tt;
ll arr[MAX], par[MAX][41], dp[MAX][41];
vector<ll> graph[MAX];

void dfs(ll node, ll p) {
    par[node][1] = p;
    for(auto v : graph[node]) if(v != p) dfs(v, node);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> l;
    for(ll i = 1; i <= n - 1; ++i) {
        ll a, b; cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(ll i = 1; i <= n; ++i) cin >> arr[i];
    for(ll i = 0; i <= n; ++i) for(ll k = 0; k <= 40; ++k) dp[i][k] = 1;
    for(ll i = 0; i <= n; ++i) par[i][0] = i;
    dfs(1, 0);
    for(ll k = 2; k <= 40; ++k) for(ll i = 1; i <= n; ++i) par[i][k] = par[par[i][k - 1]][1];
    
    
    cin >> q;
    for(ll i = 1; i <= q; ++i) {
        ll t; cin >> t;
        if(t == 1) {
            ll x, d, w; cin >> x >> d >> w;
            for(ll i = 0; i <= d; ++i) {
                dp[par[x][i]][d - i] = dp[par[x][i]][d - i] * w % l;
                if(par[x][i] == 0) break;
            }
        }
        else {
            ll x; cin >> x;
            ll ans = arr[x];
            for(ll j = 0; j <= 40; ++j) {
                if(par[x][j] == 0) {
                    for(ll k = j; k <= 40; ++k) ans = ans * dp[par[x][j]][k] % l;
                    break;
                }
                ans = ans * dp[par[x][j]][j] % l;
                if(j < 40) ans = ans * dp[par[x][j]][j + 1] % l;
            }
            cout << ans << '\n';
        }
    }
    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