Submission #1125271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125271		Icelast	Sprinkler (JOI22_sprinkler)	C++20	3 / 100	1260 ms	1114112 KiB

sprinkler

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
ll mod;
void sub1(ll n, ll L, ll Q, vector<vector<int>> adj, vector<ll> h){
    auto dfs = [&](auto dfs, int u, int p, int len, ll d, ll w) -> void{
        if(len > d) return;
        h[u] *= w;
        h[u] %= L;
        for(int v : adj[u]){
            if(v == p) continue;
            dfs(dfs, v, u, len+1, d, w);
        }
    };
    for(int i = 1; i <= Q; i++){
        ll t, x, d, w;
        cin >> t;
        if(t == 1){
            cin >> x >> d >> w;
            dfs(dfs, x, 0, 0, d, w);
        }else{
            cin >> x;
            h[x] %= L;
            cout << h[x] << "\n";
        }
    }
}
// supports: point modify, range apply, range query, walk to find first/last with some precedent
// you are to implement the 2 structs Tag and Info
// for the walks, pass a lambda that takes in Info and return true iff the node with that Info will contain the desired element

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector<Info>(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

struct Tag {
    ll mul = 1;
    void apply(const Tag &t) & {
        mul *= t.mul;
        mul%=mod;
    }
};

struct Info {
    ll val = 1;
    void apply(const Tag &t) & {
        val*=t.mul;
        val %= mod;
    }
    Info operator+(const Info &b) {
        return {val*b.val%mod};
    }
};
void subfull(ll n, ll L, ll Q, vector<vector<int>> adj, vector<ll> h){
    vector<vector<vector<ll>>> lazy(n+1, vector<vector<ll>>(41));
    vector<int> pa(n+1);
    vector<vector<pair<int, int>>> pot(n+1);
    vector<vector<int>> idx(n+1), val(n+1);
    auto dfs = [&](auto dfs, int u, int p) -> void{
        pa[u] = p;
        for(int i = 0; i < (int)adj[u].size(); i++){
            int v = adj[u][i];
            if(v == p) continue;
            pot[u].push_back({v, i});
            dfs(dfs, v, u);
        }
    };
    dfs(dfs, 1, 0);
    for(int i = 1; i <= n; i++){
        sort(pot[i].begin(), pot[i].end());
        for(auto it : pot[i]){
            idx[i].push_back(it.second);
            val[i].push_back(it.first);
        }
    }
    auto get = [&](int u, int v) -> int{
        return idx[u][lower_bound(val[u].begin(), val[u].end(), v) - val[u].begin()];
    };
    vector<vector<LazySegmentTree<Info, Tag>>> T(n+1, vector<LazySegmentTree<Info, Tag>>(41));
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 40; j++){
            T[i][j].init(adj[i].size()+1);
            lazy[i][j].resize(adj[i].size()+1, 1);
        }
    }
    ll mxD = 0;
    for(int it = 1; it <= Q; it++){
        ll t, x, d, w;
        cin >> t;
        if(t == 1){
            cin >> x >> d >> w;
            mxD = max(mxD, d);
            int N = (int)adj[x].size();
            T[x][d].rangeApply(0, N+1, {w});
            int p = x;
            for(int i = 1; i <= d; i++){
                if(pa[p] == 0) break;
                int id = get(pa[p], p);
                T[pa[p]][d-i].rangeApply(0, id, {w});
                N = adj[pa[p]].size();
                T[pa[p]][d-i].rangeApply(id+1, N+1, {w});
                p = pa[p];
            }
        }else{
            cin >> x;
            ll res = h[x]%mod;
            //cout << res << "\n"; continue;
            int N = (int)adj[x].size();
            for(int j = 0; j <= mxD; j++){
                res *= T[x][j].rangeQuery(N, N+1).val;
                res %= mod;
            }
            for(int i = 1; i <= mxD; i++){
                if(pa[x] == 0) break;
                int id = get(pa[x], x);
                for(int j = i; j <= mxD; j++){
                    res *= T[pa[x]][j].rangeQuery(id, id+1).val;
                    //cout << pa[x] << " " << j << " " << id << " " << T[pa[x]][j].rangeQuery(id, id+1).val << "s\n";


                    res %= mod;
                }
                x = pa[x];
            }
            cout << res << "\n";
        }
    }
}
void solve(){
    ll n, L, Q;
    cin >> n >> L;
    mod = L;
    vector<vector<int>> adj(n+1);
    vector<ll> h(n+1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    cin >> Q;
    subfull(n, L, Q, adj, h);
    return;
    if(n <= 1000 && Q <= 1000){
        sub1(n, L, Q, adj, h);
        return;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("GARDEN.inp", "r", stdin);
    //freopen("GARDEN.out", "w", stdout);
    solve();
}

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