Submission #1125276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125276		bruh	Sprinkler (JOI22_sprinkler)	C++20	83 / 100	4103 ms	431192 KiB

sprinkler

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 4e5 + 5;
int n, q, mod;
int a[maxn];
vector<int> adj[maxn];
array<int, 4> qr[maxn];


struct sub1{
    int d[1005][1005];
    void dfsd(int x, int p, int *d)
    {
        d[x] = d[p] + 1;
        for (int i : adj[x]) if (i != p)
            dfsd(i, x, d);
    }
    sub1()
    {
        for (int i = 1; i <= n; i++)
        {
            d[i][i] = -1;
            dfsd(i, i, d[i]);
        }
        for (int j = 1; j <= q; j++)
        {
            int t = qr[j][0], x = qr[j][1], D = qr[j][2], val = qr[j][3];
            if (t == 1)
            {
                for (int i = 1; i <= n; i++)
                    if (d[i][x] <= D)
                        a[i] = (a[i] * val) % mod;
            }
            else cout << a[x] << "\n";
        }
    }
};

struct sub23{
    int in[maxn], out[maxn], h[maxn], par[maxn];
    struct node{
        node *l, *r;
        int p;
        node(int v = 1)
        {
            l = r = 0;
            p = v;
        }
    };

    node *root[maxn];

    inline void mul(int &x, int y)
    {
        x *= y;
        x %= mod;
    }

    void upd(int lx, int rx, int val, node *id, int l = 1, int r = n)
    {
        if (lx > rx || l > rx || lx > r) return;
        if (lx <= l && r <= rx) return mul(id -> p, val);
        int mid = (l + r) / 2;
        if (!id -> l) id -> l = new node();
        if (!id -> r) id -> r = new node();
        upd(lx, rx, val, id -> l, l, mid);
        upd(lx, rx, val, id -> r, mid + 1, r);
    }

    int qry(int pos, node *id, int l = 1, int r = n)
    {
        if (!id) return 1;
        if (l == r) return id -> p;
        int mid = (l + r) / 2;
        if (pos <= mid) return (id -> p * qry(pos, id -> l, l, mid)) % mod;
        return (id -> p * qry(pos, id -> r, mid + 1, r)) % mod;
    }

    int max_depth = 0, cnt = 0;

    void dfs(int x = 1, int p = 0)
    {
        in[x] = ++cnt;
        h[x] = h[p] + 1;
        par[x] = p;
        max_depth = max(max_depth, h[x]);
        for (int i : adj[x]) if (i != p)
            dfs(i, x);
        out[x] = cnt;
    }

    inline void apply(int l, int r, int u, int v, int f, int d, int val)
    {
        for (int i = 1; i <= d; i++)
        {
            if (f + i > max_depth) return;
            if (!root[f + i]) root[f + i] = new node();
            if (u == -1) upd(l, r, val, root[f + i]);
            else upd(l, u - 1, val, root[f + i]), upd(v + 1, r, val, root[f + i]);
        }
    }

    void update(int x, int D, int val)
    {
        int d = 0;
        apply(in[x], out[x], -1, -1, h[x], D, val);
        mul(a[x], val);
        int pre = x;
        x = par[x];
        while (D--)
        {
            if (!x) return;
            apply(in[x], out[x], in[pre], out[pre], h[x], D, val);
            pre = x;
            mul(a[x], val);
            x = par[x];
        }
    }

    int solve(int x)
    {
        int ans = a[x];
        mul(ans, qry(in[x], root[h[x]]));
        return ans;
    }

    sub23()
    {
        dfs();
        for (int j = 1; j <= q; j++)
        {
            int t = qr[j][0], x = qr[j][1], D = qr[j][2], val = qr[j][3];
            if (t == 1) update(x, D, val);
            else
                cout << solve(x) << "\n";
        }
    }
};

struct sub45{
    int mark[maxn], sz[maxn], par[maxn], mu[maxn];
    vector<int> anc[maxn];

    struct DS{
        int n;
        vector<int> f;
        void reset(int _n)
        {
            n = _n;
            f.resize(n + 1, 0);
        }
        void upd(int l, int r, int val)
        {
            l = max(0ll, l - 1);
            r = min(r, n);
            if (l > r) return;
            for (; l > 0; l -= l & -l)
                f[l] -= val;
            for (; r > 0; r -= r & -r)
                f[r] += val;
        }
        int get(int x)
        {
            if (x == 0) return 0;
            int ans = 0;
            for (; x <= n; x += x & -x)
                ans += f[x];
            return ans;
        }
    } A[maxn], B[maxn];

    void get_size(int x, int p)
    {
        sz[x] = 1;
        for (int i : adj[x]) if (i != p && !mark[i])
            get_size(i, x),
            sz[x] += sz[i];
    }

    int find(int x, int p, int half)
    {
        for (int i : adj[x])
            if (i != p && !mark[i] && sz[i] > half)
                return find(i, x, half);
        return x;
    }

    void dfs(int x, int p, int c, int d)
    {
        anc[x].emplace_back(d);
        for (int i : adj[x]) if (i != p && !mark[i])
            dfs(i, x, c, d + 1);
    }

    void solve(int x, int pre)
    {
        get_size(x, x);
        int size = sz[x];
        x = find(x, x, sz[x] / 2);
        mark[x] = 1;
        par[x] = pre;
        A[x].reset(size + 5);
        B[x].reset(size + 5);
        dfs(x, x, x, 0);
        for (int i : adj[x]) if (!mark[i])
            solve(i, x);
    }

    void upd(int x, int l, int r, int val)
    {
        int u = x;
        for (int pt = 0, dist; x; x = par[x], pt++)
            dist = anc[u][pt],
            A[x].upd(l - dist + 1, r - dist + 1, val);
        x = u;
        for (int pt = 1, dist; par[x]; x = par[x], pt++)
            dist = anc[u][pt],
            B[x].upd(l - dist + 1, r - dist + 1, val);
    }

    int qry(int x)
    {
        int ans = A[x].get(1);
        int u = x;
        for (int pt = 1, dist; par[x]; x = par[x], pt++)
            dist = anc[u][pt],
            ans += A[par[x]].get(dist + 1) - B[x].get(dist + 1);
        return ans;
    }

    sub45(int one)
    {
        solve(1, 0);
        for (int i = 1; i <= n; i++)
            reverse(anc[i].begin(), anc[i].end());
        for (int i = 1; i <= n; i++)
            upd(i, 0, 0, 0);
        mu[0] = 1;
        for (int i = 1; i <= n; i++)
            mu[i] = (mu[i - 1] * one) % mod;
        for (int j = 1; j <= q; j++)
        {
            int t = qr[j][0], x = qr[j][1], D = qr[j][2], val = qr[j][3];
            if (t == 1) upd(x, 0, D, 1);
            else
                cout << a[x] * mu[qry(x)] % mod << "\n";
        }
    }


};

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("GARDEN.inp", "r", stdin);
//    freopen("GARDEN.out", "w", stdout);
    cin >> n >> mod;
    for (int i = 1, u, v; i < n; i++)
        cin >> u >> v,
        adj[u].emplace_back(v),
        adj[v].emplace_back(u);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> q;
    set<int> vq;
    for (int i = 1; i <= q; i++)
    {
        cin >> qr[i][0];
        if (qr[i][0] == 1)
            cin >> qr[i][1] >> qr[i][2] >> qr[i][3], vq.emplace(qr[i][3]);
        else cin >> qr[i][1];
    }
    if (max(n, q) <= 1000){
        sub1 bruh;
    }
    else if (vq.size() == 1)
    {
        sub45 bruh(*vq.begin());
    } else
    {
        sub23 bruh;
    }
}

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