Submission #1228839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228839		Double_Slash	Sprinkler (JOI22_sprinkler)	C++20	0 / 100	4001 ms	138048 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, L, q, seen[200001], level[200001], c[200001][18], dep[200001][18], sub[200001][18], h[200001];
vector<int> adj[200001];

void times(int &a, int b) { a = (ll) a * b % L; }

struct St {
    int n;
    vector<int> st;

    void init(int n) { st.resize((this->n = n) << 1, 1); }

    void upd(int l, int r, int v) {
        for (l += n, r = min(r, n) + n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) times(st[l++], v);
            if (r & 1) times(st[--r], v);
        }
    }

    int operator()(int i) {
        int ret = 1;
        for (i += n; i; i >>= 1) times(ret, st[i]);
        return ret;
    }
} inc[200001];
vector<St> exc[200001];

int dfs(int i, int p = 0) {
    int f = 0, f2 = 0;
    for (int j: adj[i]) {
        if (j != p) {
            int fj = dfs(j, i);
            f2 |= fj & f;
            f |= fj;
        }
    }
    level[i] = __builtin_ctz(++(f |= f2));
    return f;
}

int dfs2(int i, int r, int p) {
    c[i][level[r]] = r;
    int mx = 0;
    for (int k: adj[i]) {
        if (k != p and not seen[k]) {
            sub[k][level[r]] = sub[i][level[r]];
            dep[k][level[r]] = dep[i][level[r]] + 1;
            mx = max(mx, dfs2(k, r, i));
        }
    }
    return mx + 1;
}

int fast(int x, int n) {
    if (not n) return 1;
    int ret = fast(x, n >> 1);
    times(ret, ret);
    if (n & 1) times(ret, x);
    return ret;
}

int main() {
    cin >> n >> L;
    for (int i = n; --i;) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    dfs(1);
    int order[n];
    iota(order, order + n, 1);
    sort(order, order + n, [&] (int i, int j) { return level[i] > level[j]; });
    for (int i: order) {
        c[i][level[i]] = i;
        int mx = 1;
        for (int j: adj[i]) {
            if (seen[j]) continue;
            sub[j][level[i]] = exc[i].size();
            dep[j][level[i]] = 1;
            int mxj = dfs2(j, i, i) + 1;
            mx = max(mx, mxj);
            exc[i].emplace_back();
            exc[i].back().init(mxj);
        }
        inc[i].init(mx);
        seen[i] = true;
    }
    for (int i = 1; i <= n; ++i) cin >> h[i];
    cin >> q;
    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            int d, w;
            cin >> d >> w;
            for (int i = 18; i--;) {
                if (not c[x][i] or dep[x][i] > d) continue;
                inc[c[x][i]].upd(0, d - dep[x][i] + 1, w);
                if (x != c[x][i]) exc[c[x][i]][sub[x][i]].upd(0, d - dep[x][i] + 1, w);
            }
        } else {
            int ans = h[x];
            for (int i = 18; i--;) {
                if (not c[x][i]) continue;
                times(ans, inc[c[x][i]](dep[x][i]));
                if (x != c[x][i]) times(ans, fast(exc[c[x][i]][sub[x][i]](dep[x][i]), L - 2));
            }
            cout << ans << endl;
        }
    }
}

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