Submission #1247588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247588		lrnnz	Sprinkler (JOI22_sprinkler)	C++20	0 / 100	0 ms	320 KiB

sprinkler

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <queue>
#include <random>
using namespace std;

#define all(a) (a).begin(), (a).end()
#define ll long long
#define ld long double
#define ui uint64_t
#define cont(set, element) ((set).find(element) != (set).end())
#define pb push_back

#define chmin(x, y) (x = min(x, y)) 
#define chmax(x, y) (x = max(x, y))

/********* DEBUG *********/

template <typename T>
void outvec(const vector<T>& Z){
    for (const T& x : Z)
    cout << x << ' ';
    cout << "\n";
}
void printVariable(const any& var) {
    if (!var.has_value()) {
        cout << "null";
        return;
    }

    if (var.type() == typeid(int)) {
        cout << any_cast<int>(var);
    } else if (var.type() == typeid(double)) {
        cout << any_cast<double>(var);
    } else if (var.type() == typeid(float)) {
        cout << any_cast<float>(var);
    } else if (var.type() == typeid(char)) {
        cout << any_cast<char>(var);
    } else if (var.type() == typeid(bool)) {
        cout << (any_cast<bool>(var) ? "true" : "false");
    } else if (var.type() == typeid(string)) {
        cout << any_cast<string>(var);
    } else if (var.type() == typeid(const char*)) {
        cout << any_cast<const char*>(var);
    } else if (var.type() == typeid(long long)) {
        cout << any_cast<long long>(var);
    } else {
        cout << "[unknown type]";
    }
}


template<typename... Args>
void outval(Args... args) {
    vector<any> variables = {args...};
    
    for (size_t i = 0; i < variables.size(); ++i) {
        printVariable(variables[i]);
        if (i != variables.size() - 1) {
            cout << " ";
        }
    }
    cout << "\n";
}

#define sp << " " <<
#define fi first
#define se second

/********* DEBUG *********/

const ll MOD2 = 1e9 + 7;
const ll MOD = 998244353;
const ll inf = 1e18;

// from, curr, val, time, decreasing
struct update{
    ll from, val, tm;
    bool decreasing;
};


ll up[200005][19];
void dfs(ll u, ll p, ll curdep, vector<vector<ll>> &adj, vector<ll> &depth){
    depth[u] = curdep;
    for (auto &v : adj[u]){
        if (v == p)
            continue;

        up[v][0] = u;
        dfs(v, u, curdep + 1, adj, depth);
    }
}

ll kth(ll x, ll k){
    for (int i = 0; i < 19; i++){
        if (k & (1 << i))
            x = up[x][i];

        if (x == -1)
            return 0;
    }

    return x;
}

void solve(){
    ll n, mod;
    cin >> n >> mod;

    vector<vector<ll>> adj(n);
    for (int i = 0; i < n-1; i++){
        ll a,b;
        cin >> a >> b;

        a--; b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    vector<ll> vals(n), depth(n);
    for (auto &i : vals)
        cin >> i;

    // root at 0, create binlift
    dfs(0, -1, 0, adj, depth);
    for (int i = 0; i < 19; i++)
        up[0][i] = -1;

    for (int i = 1; i < 19; i++){
        for (int j = 0; j < n; j++){
            up[j][i] = up[ up[j][i-1] ][i-1];
        }
    }

    ll q;
    cin >> q;
    
    map<ll, vector<update>> mp;

    auto walk = [&](ll u) -> void {
        ll cur = kth(u, 41);
        while (true){
            //outval("cur:",cur);
            for (auto &[from, val, tm, decreasing] : mp[cur]){
                vals[cur] = (vals[cur] * val) % mod;

                //outval("upd,from,val,tm,decr:",from,val,tm,decreasing);
                if (decreasing && tm <= 0)
                    continue;
                
                for (auto &v : adj[cur]){
                    if (v == up[cur][0])
                        continue;

                    ll diff = depth[from]-depth[v];
                    if (decreasing || diff < 0){
                        if (tm-1 >= 0)
                            mp[v].pb({from, val, tm-1, true});
                    }
                    else{
                        if (v == kth(from, diff)){
                            mp[v].pb({from, val, tm+1, false});
                        }
                        else{
                            if (tm-1 >= 0)
                                mp[v].pb({from, val, tm-1, true});
                        }
                    }
                }
            }

            mp[cur].clear();
            if (cur == u)
                return;

            cur = kth(u, depth[u]-depth[cur]-1);
        }
    };

    while (q--){
        ll t;
        cin >> t;

        if (t == 1){
            ll x,d,w;
            cin >> x >> d >> w;

            x--;
            ll to = kth(x, d);
            update upd = {x, w, max(0LL, d-(depth[x]-depth[to])), false};
            //outval("to,tm:",to,upd.tm);

            mp[to].pb(upd);
        }
        else{
            ll y;
            cin >> y;
            y--;

            walk(y);
            outval(vals[y]);
        }
    }
} 

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

    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

}    

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