Submission #1097023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097023		efishel	Sprinkler (JOI22_sprinkler)	C++17	3 / 100	4115 ms	595028 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 2.1E5, MAXD = 42;
vll adj[MAXN];
ll L;
ll ve[MAXN];
map <ll, ll> dp[MAXN]; // children of u at depth j should be multed by dp[u][j]
ll par[MAXN], dep[MAXN];

void dfs (ll u, ll par) {
    ::par[u] = par;
    for (ll d = dep[u]; d <= dep[u]+MAXD; d++) dp[u][d] = 1;
    for (ll v : adj[u]) {
        if (v == par) continue;
        dep[v] = dep[u]+1;
        dfs(v, u);
    }
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n;
    cin >> n >> L;
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        u += 50; v += 50;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (ll i = 1+50; i <= n+50; i++) cin >> ve[i];
    for (ll i = 0; i <= 50; i++) adj[i].push_back(i+1);
    dep[0] = 0;
    dfs(0, 0);
    ll Q;
    cin >> Q;
    for (ll q = 0; q < Q; q++) {
        char type;
        cin >> type;
        switch (type) {
            case '1':
            {ll u, maxD, w;
            cin >> u >> maxD >> w;
            u += 50;
            ll uo = u;
            for (ll d = 0; d < maxD; d++) {
                (dp[u][dep[uo]+maxD-2*d] *= w) %= L;
                (dp[u][dep[uo]+maxD-2*d-1] *= w) %= L;
                u = par[u];
            }
            (dp[u][dep[u]] *= w) %= L;
            break;}
            case '2':
            {ll u;
            cin >> u;
            u += 50;
            ll uo = u;
            ll ans = ve[u];
            for (ll i = 0; i < MAXD; i++, u = par[u]) {
                (ans *= dp[u][dep[uo]]) %= L;
            }
            cout << ans << '\n';
            break;}
        }
    }
    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