Submission #678999

#	Time	Username	Problem	Language	Result	Execution time	Memory
678999		jhwest2	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	2990 ms	184572 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

const int N = 202020;
const int M = 44;

int n, mod, q;
vector<int> g[N];

int sub[N], dep[N], gp[N], a[N];
bool dead[N];

void pre_dfs(int p, int v) {
    sub[v] = 1;
    for (int x : g[v]) {
        if (p == x || dead[x])
            continue;

        pre_dfs(v, x);
        sub[v] += sub[x];
    }
}
int find_centroid(int p, int v, int z) {
    for (int x : g[v]) {
        if (p == x || dead[x])
            continue;
        
        if (2 * sub[x] > z)
            return find_centroid(v, x, z);
    }
    return v;
}
void dfs(int p, int v, int z) {
    gp[v] = z;
    dep[v] = dep[p] + 1;
    for (int x : g[v]) {
        if (p == x || dead[x])
            continue;

        dfs(v, x, z);
    }
}
struct query {
    int t, x, d, w, i;
};
vector<query> qr[N];
int ans[2 * N];

struct fenwick {
    int tree[N];

    void init(int sz) {
        fill(tree, tree + sz + 1, 1);
    }
    void update(int a, int x) {
        for (; a < N; a += a & -a) 
            tree[a] = 1ll * tree[a] * x % mod;
    }
    int query(int a) {
        int res = 1;
        for (; a; a -= a & -a)
            res = 1ll * res * tree[a] % mod;
        return res;
    }
} t1[M], t2[M];

void solve(int v) {
    pre_dfs(v, v);
    int centroid = find_centroid(v, v, sub[v]);

    dep[centroid] = 0;
    for (int i = 0; i < g[centroid].size(); i++)
        if (!dead[g[centroid][i]]) 
            dfs(centroid, g[centroid][i], i);

    if (v != centroid) {
        qr[centroid] = qr[v];
        vector<query>().swap(qr[v]);
    }

    int sz = g[centroid].size();

    for (int i = 0; i < M; i++) {
        t1[i].init(sz);
        t2[i].init(sz);
    }

    vector<int> s(M, 1);
    for (auto [t, x, d, w, i] : qr[centroid]) {
        if (x != centroid)
            qr[g[centroid][gp[x]]].push_back({t, x, d, w, i});

        if (t == 1) {
            if (dep[x] > d)
                continue;
            if (x == centroid)
                s[d] = 1ll * s[d] * w % mod;
            else {
                t1[d - dep[x]].update(gp[x] + 1, w);
                t2[d - dep[x]].update(sz - gp[x], w);
            }
            // cout << v << ' ' << centroid << ' ' << x << ' ' << d - dep[x] << ' ' << gp[x] << ' ' << w << '\n';
        }
        else {
            for (int j = dep[x]; j < M; j++) {
                if (x == centroid)
                    ans[i] = 1ll * ans[i] * t1[j].query(sz) % mod;
                else {
                    if (gp[x]) 
                        ans[i] = 1ll * ans[i] * t1[j].query(gp[x]) % mod;
                    if (gp[x] != sz - 1) 
                        ans[i] = 1ll * ans[i] * t2[j].query(sz - gp[x] - 1) % mod;
                }
                ans[i] = 1ll * ans[i] * s[j] % mod;
            }
        }
    }
    dead[centroid] = 1;

    for (int i = 0; i < g[centroid].size(); i++)
        if (!dead[g[centroid][i]])
            solve(g[centroid][i]);
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> mod;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    cin >> q;
    int sz = 0;
    for (int i = 1; i <= q; i++) {
        int t; cin >> t;
        if (t == 1) {
            int x, d, w; cin >> x >> d >> w;
            qr[1].push_back({t, x, d, w, 0});
        }
        else {
            int x; cin >> x;
            qr[1].push_back({t, x, 0, 0, ++sz});
            ans[sz] = a[x] % mod;
        }
    }

    solve(1);

    for (int i = 1; i <= sz; i++)
        cout << ans[i] << '\n';

}

Compilation message (stderr)

sprinkler.cpp: In function 'void solve(int)':
sprinkler.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < g[centroid].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < g[centroid].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~

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