Submission #1224915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224915		minhpk	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	943 ms	175052 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 400000 + 5;

int n, q;
ll mod;
vector<ll> fenw[MAXN][3];
vector<int> og[MAXN];
vector<pair<int,int>> adj[MAXN];
ll arr[MAXN];
int cnt;
int sz[MAXN], dt[20][MAXN], lvl[MAXN], hei[MAXN], del[MAXN];
pair<int,int> par[MAXN];

void update_f(int o, int u, int x, ll v) {
    int szf = fenw[o][u].size();
    int idx = szf - x - 1;
    idx = max(idx, 1);
    for (; idx < szf; idx += idx & -idx)
        fenw[o][u][idx] = fenw[o][u][idx] * v % mod;
}

ll query_f(int o, int u, int x) {
    int szf = fenw[o][u].size();
    int idx = szf - x - 1;
    idx = min(idx, szf - 1);
    if (idx <= 0) return 1;
    ll res = 1;
    for (; idx > 0; idx -= idx & -idx)
        res = res * fenw[o][u][idx] % mod;
    return res;
}

void build_chain(int u, int p) {
    int d = u, num = 0;
    for (int v : og[u]) {
        if (v == p) continue;
        num++;
        if (num == 1) {
            adj[u].emplace_back(v,1);
            adj[v].emplace_back(u,1);
            build_chain(v,u);
        } else {
            adj[cnt].emplace_back(d,0);
            adj[d].emplace_back(cnt,0);
            adj[cnt].emplace_back(v,1);
            adj[v].emplace_back(cnt,1);
            d = cnt;
            cnt++;
            build_chain(v,u);
        }
    }
}

int dfs_size(int u, int p) {
    sz[u] = 1;
    for (auto &pr : adj[u]) {
        int v = pr.first;
        if (v == p || del[v]) continue;
        sz[u] += dfs_size(v,u);
    }
    return sz[u];
}

int find_cent(int u, int p, int tsz) {
    for (auto &pr : adj[u]) {
        int v = pr.first;
        if (v == p || del[v]) continue;
        if (sz[v] * 2 > tsz) return find_cent(v,u,tsz);
    }
    return u;
}

int dfs_cent(int u, int p, int l, int d) {
    dt[l][u] = d;
    int h = 1;
    for (auto &pr : adj[u]) {
        int v = pr.first, w = pr.second;
        if (v == p || del[v]) continue;
        h = max(h, dfs_cent(v,u,l,d+w)+1);
    }
    return h;
}

int decomp(int u, int l) {
    int tsz = dfs_size(u,-1);
    int c = find_cent(u,-1,tsz);
    del[c] = 1;
    lvl[c] = l;
    hei[c] = 1;
    int idx = -1;
    for (auto &pr : adj[c]) {
        idx++;
        int v = pr.first, w = pr.second;
        if (del[v]) continue;
        int h = dfs_cent(v,c,l,w) + 1;
        fenw[c][idx].assign(h+5,1);
        hei[c] = max(hei[c], h);
    }
    idx = -1;
    for (auto &pr : adj[c]) {
        idx++;
        int v = pr.first;
        if (del[v]) continue;
        int child = decomp(v,l+1);
        par[child] = {c, idx};
    }
    return c;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> mod;
    for (int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        og[u].push_back(v);
        og[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> arr[i];

    cnt = n+1;
    build_chain(1,-1);
    n = cnt-1;
    int rt = decomp(1,0);
    par[rt] = {-1,-1};

    cin >> q;
    while(q--){
        int cmd;
        cin >> cmd;
        if (cmd == 1) {
            int x,d;
            ll k;
            cin >> x >> d >> k;
            int l = lvl[x], cur = x, prev = -1;
            while (l >= 0) {
                if (dt[l][x] <= d) {
                    arr[cur] = arr[cur] * k % mod;
                    for (int i = 0; i < (int)adj[cur].size(); i++){
                        if (i == prev) continue;
                        update_f(cur, i, d - dt[l][x], k);
                    }
                }
                prev = par[cur].second;
                cur = par[cur].first;
                l--;
            }
        } else {
            int x;
            cin >> x;
            ll ans = arr[x] % mod;
            int l = lvl[x], cur = x, prev = -1;
            while (l > 0) {
                prev = par[cur].second;
                cur = par[cur].first;
                l--;
                ans = ans * query_f(cur, prev, dt[l][x]) % mod;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

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