Submission #1229840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229840		Double_Slash	Sprinkler (JOI22_sprinkler)	C++20	3 / 100	2995 ms	1114112 KiB

sprinkler

#pragma GCC optimize("O3,unroll-loops,inline")
#pragma GCC target("avx2")
#include "immintrin.h"
#include <bits/stdc++.h>

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

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

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

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

struct Int {
    ull x;
    __m256i a;
    ull b;

    Int() : Int(1) {}

    Int(unsigned _x) : x(_x) {
        unsigned cnt[12]{};
        for (unsigned i = FACT.size(); i--;) {
            while (x % FACT[i] == 0) {
                cnt[i]++;
                x /= FACT[i];
            }
        }
        a = _mm256_loadu_si256((__m256i*) cnt);
        b = *(ull*) (cnt + 8);
    }

    operator unsigned() const {
        unsigned cnt[12];
        _mm256_storeu_si256((__m256i*) cnt, a);
        ull ret = x;
        for (unsigned i = FACT.size(); i--;) ret = ret * lookup(i, cnt[i]) % L;
        return ret;
    }

    void operator*=(const Int &o) {
        x = x * o.x % L;
        a = _mm256_add_epi32(a, o.a);
        b += o.b;
    }

    void operator/=(const Int &o) {
        x = x * fast(o.x, totient - 1) % L;
        a = _mm256_sub_epi32(a, o.a);
        b -= o.b;
    }
};

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

    void init(unsigned n) { st.resize((this->n = 1 << __lg(n * 2 - 1)) << 1, 1); }

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

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

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

unsigned dfs2(unsigned i, unsigned r, unsigned p) {
    c[i][level[r]] = r;
    unsigned mx = 0;
    for (unsigned 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() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> L;
    for (int i = 2, l = L; i <= l; ++i) {
        if (i * i > l) {
            FACT.emplace_back(l);
            break;
        }
        if (l % i == 0) {
            FACT.emplace_back(i);
            while (l % i == 0) l /= i;
        }
    }
    sort(all(FACT));
    FACT.erase(unique(all(FACT)), FACT.end());
    for (int p: FACT) {
        unsigned cnt = 0;
        for (unsigned l = L; l % p == 0; l /= p) ++cnt;
        for (unsigned i = cnt; --i;) totient *= p;
        totient *= (p - 1);
    }
    for (unsigned i = FACT.size(); i--;) mem[i] = {1};
    for (unsigned i = n; --i;) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    dfs(1);
    unsigned order[n];
    iota(order, order + n, 1);
    sort(order, order + n, [&] (int i, int j) { return level[i] > level[j]; });
    for (unsigned i: order) {
        c[i][level[i]] = i;
        unsigned mx = 1;
        for (unsigned j: adj[i]) {
            if (seen[j]) continue;
            sub[j][level[i]] = exc[i].size();
            dep[j][level[i]] = 1;
            unsigned 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 (unsigned i = 1; i <= n; ++i) cin >> h[i];
    cin >> q;
    while (q--) {
        unsigned t, x;
        cin >> t >> x;
        if (t == 1) {
            unsigned d, raw;
            cin >> d >> raw;
            Int w{raw ? raw : L};
            for (unsigned i = 18; i--;) {
                if (not c[x][i] or dep[x][i] > d) continue;
                inc[c[x][i]].upd(d - dep[x][i] + 1, w);
                if (x != c[x][i]) exc[c[x][i]][sub[x][i]].upd(d - dep[x][i] + 1, w);
            }
        } else {
            Int ans{h[x]}, inv;
            for (unsigned 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]);
            }
            ans /= inv;
            cout << (unsigned) ans << '\n';
        }
    }
}

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