Submission #721471

#	Time	Username	Problem	Language	Result	Execution time	Memory
721471		becaido	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	892 ms	58024 KiB

sprinkler

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;
const int MAX = 41;

int n, mod, q;
int a[SIZE];
vector<int> adj[SIZE];
int pa[SIZE], val[SIZE][MAX];

void solve() {
    cin >> n >> mod;
    FOR (i, 2, n) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    FOR (i, 1, n) {
        cin >> a[i];
        fill(val[i], val[i] + MAX, 1);
    }
    auto dfs = [&](auto dfs, int pos)->void {
        for (int np : adj[pos]) if (np != pa[pos]) {
            pa[np] = pos;
            dfs(dfs, np);
        }
    };
    dfs(dfs, 1);
    cin >> q;
    while (q--) {
        int ty, x, d, w;
        cin >> ty;
        if (ty == 1) {
            cin >> x >> d >> w;
            for (int pos = x, i = d; i >= 0; i--) {
                val[pos][i] = 1ll * val[pos][i] * w % mod;
                if (i >= 1) val[pos][i - 1] = 1ll * val[pos][i - 1] * w % mod;
                if (pos == 1) i--;
                else pos = pa[pos];
            }
        }
        if (ty == 2) {
            cin >> x;
            int ans = a[x];
            for (int pos = x, i = 0; pos && i < MAX; pos = pa[pos], i++) ans = 1ll * ans * val[pos][i] % mod;
            cout << ans << '\n';
        }
    }
}

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