Submission #1224897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224897		minhpk	Sprinkler (JOI22_sprinkler)	C++20	0 / 100	21 ms	47432 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;
int a, mod;
vector<int> z[1000005];
int h[1000005];
int sta[1000005];
int fin[1000005];
int tour;
vector<int> depth[1000005];
int par[1000005];
int high[1000005];
int base[1000005];
int maxdepth = 0;

static inline int addMod(int a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

static inline int mulMod(int a, int b) {
    return int((long long)a * b % mod);
}

void dfs(int i, int j, int k) {
    par[i] = j;
    tour++;
    sta[i] = tour;
    maxdepth = max(maxdepth, k);
    depth[k].push_back(sta[i]);
    for (auto p : z[i]) if (p != j) {
        high[p] = high[i] + 1;
        dfs(p, i, k + 1);
    }
    fin[i] = tour;
}

int f[4000005];
int lazy[4000005];

void push(int id) {
    if (lazy[id] != 1) {
        int t = lazy[id];
        lazy[id<<1] = mulMod(lazy[id<<1], t);
        lazy[id<<1|1] = mulMod(lazy[id<<1|1], t);
        lazy[id] = 1;
    }
}

void update(int id, int l, int r, int x, int y, int val) {
    if (x > r || y < l) return;
    if (l >= x && r <= y) {
        lazy[id] = mulMod(lazy[id], val);
        return;
    }
    int mid = (l + r) >> 1;
    push(id);
    update(id<<1, l, mid, x, y, val);
    update(id<<1|1, mid+1, r, x, y, val);
}

int get(int id, int l, int r, int pos) {
    if (l == r) return lazy[id];
    push(id);
    int mid = (l + r) >> 1;
    if (pos <= mid) return get(id<<1, l, mid, pos);
    else return get(id<<1|1, mid+1, r, pos);
}

int sbd(int i) {
    int res = base[high[i]];
    int t = high[i];
    int pre = lower_bound(depth[t].begin(), depth[t].end(), sta[i]) - depth[t].begin() + 1;
    res += pre;
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> mod;
    for (int i = 1; i < a; i++) {
        int x, y;
        cin >> x >> y;
        z[x].push_back(y);
        z[y].push_back(x);
    }
    for (int i = 1; i <= a; i++) cin >> h[i];
    dfs(1, 0, 1);
    for (int i = 1; i <= maxdepth; i++) {
        base[i] = base[i-1] + depth[i-1].size();
        sort(depth[i].begin(), depth[i].end());
    }
    for (int i = 0; i < 4 * a + 5; i++) {
        lazy[i] = 1;
    }
    int q;
    cin >> q;
    while (q--) {
        int c;
        cin >> c;
        if (c == 2) {
            int x;
            cin >> x;
            int pos = sbd(x);
            int mul = get(1, 1, a, pos);
            cout << mulMod(h[x], mul) << '\n';
        } else {
            int x, d, w;
            cin >> x >> d >> w;
            int t = high[x];
            for (int i = 1; i <= maxdepth; i++) {
                int dist = abs(i - t);
                if (dist > d) continue;
                int L = base[i] + 1;
                int R = base[i] + depth[i].size();
                if (L <= R) update(1, 1, a, L, R, w);
            }
        }
    }
    return 0;
}

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