Submission #544702

#	Time	Username	Problem	Language	Result	Execution time	Memory
544702		kevinxiehk	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1084 ms	93796 KiB

sprinkler

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define iint long long
#define int long long
#define inf 1e18
#define ick cout<<"ickbmi32.9\n"
using namespace std;
int mod;
int n;
vector<int> conn[200005];
int fa[200005];
// unordered_map<int, iint> no[200005][4]; // no[fa][dist][chd] = need
iint h[200005];
iint mul[200005][45];
// iint bm(iint a, iint b) {
//     if(b == 0) return 1; 
//     iint t = bm(a, b / 2); 
//     t = t * t % mod; 
//     return (b % 2 == 1 ? t * a % mod : t);
// }
// int phi(int n) {
//     iint result = n;
//     for(int p = 2; p * p <= n; p++) {
//         if (n % p == 0) {
//             while (n % p == 0) n /= p; 
//             result = result * (p - 1) / p;
//         }
//     }
//     if (n > 1) result = result * (n - 1) / n;
//     return result;
// }
// int phimod;
// int inv(int a) {return bm(a, phimod - 1);}
void dfs(int now, int f) {
    for(auto x: conn[now]) {
        if(x == f) continue;
        // for(int i = 0; i <= 41; i++) no[now][i][x] = 1;
        fa[x] = now;
        dfs(x, now);
    }
}

int getres(int id, int di, int fm) {
    iint res = 1;
    if(id != 1) res = res * mul[id][di] % mod * mul[id][di + 1] % mod;
    else for(int i = di; i <= 40; i++) res = res * mul[1][i] % mod;
    // if(fm != -1) {
    //     for(int i = di; i <= 3; i++) res = res * no[id][i][fm] % mod;
    // } 
    if(di < 40 && fa[id] != 0) res = res * getres(fa[id], di + 1, id) % mod;
    return res % mod;
}   

// int invk;

void updval(int id, int di, int fm, int k) {
    mul[id][di] = mul[id][di] * k % mod;
    // if(fm != -1) no[id][di][fm] = no[id][di][fm] * invk % mod;
    if(di == 0 || fa[id] == 0) return;
    updval(fa[id], di - 1, id, k);
}   

signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    cin >> n >> mod;
    // phimod = phi(mod);
    int t, tt, ttt;
    for(int i = 1; i < n; i++) {
        cin >> t >> tt;
        conn[t].pb(tt);
        conn[tt].pb(t);
    }
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) for(int j = 0; j <= 41; j++) mul[i][j] = 1;
    dfs(1, 1);
    int q;
    cin >> q;
    while(q--) {
        cin >> t;
        if(t == 1) {
            cin >> t >> tt >> ttt;
            // invk = inv(ttt);
            updval(t, tt, -1, ttt);
        }
        else {
            cin >> t;
            cout << h[t] * getres(t, 0, -1) % mod << '\n';
        }
    }
    return 0; 
}

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