제출 #1266271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266271		tvgk	Sprinkler (JOI22_sprinkler)	C++20	100 / 100	609 ms	100756 KiB

sprinkler

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7;

int n, MOD, par[mxN], h[mxN];
ll mem[mxN][50];
vector<int> w[mxN];

void Build(int j)
{
    for (int i : w[j])
    {
        if (i == par[j])
            continue;

        par[i] = j;
        Build(i);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> MOD;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        w[u].push_back(v);
        w[v].push_back(u);
    }
    Build(1);

    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
        for (int j = 0; j <= 41; j++)
            mem[i][j] = 1;
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int tt, ver;
        cin >> tt >> ver;

        if (tt == 1)
        {
            int dis, mul;
            cin >> dis >> mul;

            while (ver && dis >= 0)
            {
                mem[ver][dis] = mem[ver][dis] * mul % MOD;
                dis--;
                ver = par[ver];
            }
        }
        else
        {
            int dis = 0;
            ll ans = h[ver];
            while (dis <= 40)
            {
                ans = ans * mem[ver][dis] % MOD;
                if (ver != 1)
                {
                    ans = ans * mem[ver][dis + 1] % MOD;
                    ver = par[ver];
                }
                dis++;
            }
            cout << ans << '\n';
        }
    }
}

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