Submission #1241032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241032		ProtonDecay314	Sprinkler (JOI22_sprinkler)	C++20	3 / 100	4094 ms	17872 KiB

sprinkler

#pragma GCC optimize("O3", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

ll MOD = 1ll;

int main() {
    ll n;
    cin >> n >> MOD;

    vvll adj(n, vll());

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

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

    vll h(n, 0ll);

    for(ll& v : h) cin >> v;

    ll q;
    cin >> q;

    while(q--) {
        int qtype;
        cin >> qtype;

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

            vb vis(n, false);
            queue<pll> q;
            q.push({x, 0ll});

            while(!q.empty()) {
                auto [i, cd] = q.front();
                q.pop();

                if(vis[i]) continue;
                if(cd > d) continue;
                vis[i] = true;
                h[i] = (h[i] * w) % MOD;

                for(ll j : adj[i]) {
                    q.push({j, cd + 1ll});
                }
            }

        } else {
            ll x;
            cin >> x;
            x--;

            cout << h[x] << "\n";
        }
    }

    cout << flush;

    return 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