Submission #1120021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120021		dwuy	Sprinkler (JOI22_sprinkler)	C++14	3 / 100	4136 ms	796716 KiB

sprinkler

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

const int MX = 200005;
int n, q, MOD;
vector<int> G[MX];
int p[MX], r[MX], h[MX], id[MX];

int add(int a, int b){
    return (a += b) + (a >= MOD? -MOD : a<0? MOD : 0);
}

int mul(int a, int b){
    return 1LL * a * b % MOD;
}

struct SMT{
    int n;
    vector<int> tree;

    SMT(int n = 0) : n(n), tree(n<<2|3, 1) {}

    void down(int id){
        if(tree[id] == 1) return;
        int delta = tree[id];
        tree[id<<1] = mul(tree[id<<1], delta);
        tree[id<<1|1] = mul(tree[id<<1|1], delta);
        tree[id] = 1;
    }

    void update(int l, int r, int id, const int &pos, const int &val){
        if(l == pos && r == pos) return;
        if(r < pos || l > pos){
            tree[id] = mul(tree[id], val);
            return;
        }
        down(id);
        int mid = (l + r)>>1;
        update(l, mid, id<<1, pos, val);
        update(mid + 1, r, id<<1|1, pos, val);
    }

    void update(int pos, int val){
        update(1, n, 1, pos, val);
    }

    int get(int pos){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            down(id);
            if(pos <= mid) hi = mid, id = id<<1;
            else lo = mid + 1, id = id<<1 | 1;
        }
        return tree[id];
    }
} f[MX][41];

void dfs(int u){
    for(int i=0; i<(int)G[u].size(); i++) if(G[u][i] != p[u]){
        int v = G[u][i];
        p[v] = u;
        id[v] = i + 1;
        dfs(v);
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(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 >> h[i];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=40; j++){
            f[i][j] = SMT(G[i].size());
        }
    }
    for(int i=1; i<=n; i++) r[i] = 1;
    dfs(1);
    cin >> q;
    while(q--){
        int oper;
        cin >> oper;
        if(oper == 1){
            int u, d, w;
            cin >> u >> d >> w;
            r[u] = mul(r[u], w);
            f[u][d].update(0, w);
            while(d--){
                int v = p[u];
                f[v][d].update(id[u], w);
                r[v] = mul(r[v], w);
                u = v;

            }
        }
        if(oper == 2){
            int u; cin >> u;
            int res = mul(h[u], r[u]);
            for(int d=1; d<=40 && u != 1; d++){
                int v = p[u];
                for(int i=d; i<=40; i++) res = mul(res, f[v][i].get(id[u]));
                u = v;
            }
            cout << res << '\n';
        }
    }

    return 0;
}

 

Compilation message (stderr)

sprinkler.cpp: In function 'int add(int, int)':
sprinkler.cpp:10:15: warning: operation on 'a' may be undefined [-Wsequence-point]
   10 |     return (a += b) + (a >= MOD? -MOD : a<0? MOD : 0);
      |            ~~~^~~~~

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