Submission #1228962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228962		Double_Slash	Sprinkler (JOI22_sprinkler)	C++20	0 / 100	1835 ms	1114112 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()

int n, L, q, seen[200001], level[200001], c[200001][18], dep[200001][18], sub[200001][18], h[200001], totient = 1;
vector<int> FACT{0}, mem[10], adj[200001];

int lookup(int i, int n) {
    if (mem[i].size() <= n) {
        mem[i].reserve(n + 1);
        while (mem[i].size() <= n) mem[i].emplace_back((ll) mem[i].back() * FACT[i] % L);
    }
    return mem[i][n];
}

int fast(int x, int n) {
    if (not n) return 1;
    int ret = fast(x, n >> 1);
    ret = (ll) ret * ret % L;
    if (n & 1) ret = (ll) ret * x % L;
    return ret;
}

struct Int {
    int x;
    vector<int> cnt;

    Int() : Int(1) {}

    Int(int _x) : x(_x), cnt(FACT.size()) {
        if (not _x) {
            cnt[0] = x = 1;
            return;
        }
        for (int i = FACT.size(); --i;) {
            while (x % FACT[i] == 0) {
                cnt[i]++;
                x /= FACT[i];
            }
        }
    }

    operator int() const {
        if (cnt[0]) return 0;
        int ret = x;
        for (int i = FACT.size(); --i;) {
            // cerr << cnt[i] << endl;
            ret = (ll) ret * lookup(i, cnt[i]) % L;
            // cerr << "!\n";
        }
        return ret;
    }

    void operator*=(const Int &o) {
        x = (ll) x * o.x % L;
        for (int i = FACT.size(); i--;) cnt[i] += o.cnt[i];
    }

    void operator/=(const Int &o) {
        x = (ll) x * fast(o.x, totient - 1) % L;
        for (int i = FACT.size(); i--;) cnt[i] -= o.cnt[i];
    }
};

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

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

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

    Int operator()(int i) {
        // cerr << (int) st[n] << endl;
        Int ret;
        for (i += n; i; i >>= 1) {
            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 |= ((1 << __lg(f2 << 1 | 1)) - 1)));
    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 main() {
    cin >> n >> L;
    for (int i = 2; i * i <= L; ++i) {
        if (L % i == 0) {
            FACT.emplace_back(i);
            FACT.emplace_back(L / i);
        }
    }
    if (FACT.size() == 1) totient = L - 1;
    else {
        sort(all(FACT));
        FACT.erase(unique(all(FACT)), FACT.end());
        for (int p: FACT) {
            if (not p) continue;
            int l = L, cnt = 0;
            for (int l = L; l % p == 0; l /= p) ++cnt;
            for (int i = cnt; --i;) totient *= p;
            totient *= (p - 1);
        }
    }
    for (int i = FACT.size(); --i;) mem[i] = {1};
    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, raw;
            cin >> d >> raw;
            Int w{raw};
            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]}, inv;
            for (int i = 18; i--;) {
                if (not c[x][i]) continue;
                ans *= inc[c[x][i]](dep[x][i]);
                if (x != c[x][i]) inv *= exc[c[x][i]][sub[x][i]](dep[x][i]);
            }
            // cerr << (int) ans << ' ' << (int) inv << endl;
            ans /= inv;
            cout << (int) 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