Submission #1038341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038341		Sharky	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	714 ms	110140 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 200045;
const int K = 45;

int n, l, q, h[N], val[N][K], pa[N], dep[N];
vector<int> adj[N];

void dfs(int u, int p) {
    for (int v : adj[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        pa[v] = u, dfs(v, u);
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> l;
    for (int i = 0; i < N; i++) for (int j = 0; j < K; j++) val[i][j] = 1;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    pa[1] = 0;
    for (int i = n + 1; i <= n + 39; i++) {
        adj[i].push_back(i + 1);
        adj[i + 1].push_back(i);
    }
    adj[n + 40].push_back(1);
    adj[1].push_back(n + 40);
    dfs(n + 1, -1);
    for (int i = 1; i <= n; i++) cin >> h[i];
    cin >> q;
    while (q--) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int u, d, w;
            cin >> u >> d >> w;
            d = min(d, dep[u]);
            vector<int> tr;
            for (int j = 0; j <= d; j++) tr.push_back(u), u = pa[u];
            reverse(tr.begin(), tr.end());
            int dp = 0;
            val[tr[0]][0] = (val[tr[0]][0] * w) % l;
            // cout << "upd " << tr[0] << " " << 0 << " " << w << "\n";
            for (auto x : tr) {
                if (x == tr[0]) continue;
                // cout << "x: " << x << '\n';
                val[x][dp] = (val[x][dp] * w) % l;
                val[x][dp + 1] = (val[x][dp + 1] * w) % l;
                // cout << "upd " << x << " " << dp << "\n";
                // cout << "upd " << x << " " << dp + 1 << '\n';
                ++dp;
            }
        } else {
            int u;
            cin >> u;
            int ans = h[u];
            for (int i = 0; i <= 40; i++) {
                ans *= val[u][i];
                ans %= l;
                u = pa[u];
                if (!u) break;
            }
            cout << ans << '\n';
        }
    }
}

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