Submission #551403

#	Time	Username	Problem	Language	Result	Execution time	Memory
551403		BalintR	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	700 ms	63296 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cout << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cout << #arr; FR(_i, n) cout << ' ' << arr[_i]; cout << endl;}

const int MN = 2e5 + 5;
const int H = 40;
int n, mod, q;
vi adjList[MN];
int par[MN];
int init[MN];
int arr[MN][H+2];

void dfs(int n1){
    for(int n2 : adjList[n1]){
        if(n2 != par[n1]) par[n2] = n1, dfs(n2);
    }
}

int main(){
    boost();
    cin >> n >> mod;
    FR(i, n-1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        adjList[a].pb(b);
        adjList[b].pb(a);
    }
    FR(i, n) cin >> init[i];

    par[0] = -1;
    dfs(0);
    fill_n(arr[0], MN*(H+2), 1);

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

        if(type == 1){
            int a, d, v;
            cin >> a >> d >> v;
            a--;
            while(a >= 0 && d >= 0){
                arr[a][d] = (ll) arr[a][d] * v % mod;
                a = par[a];
                d--;
            }
        }
        else {
            int a; cin >> a; a--;
            ll res = init[a];
            int d = 0;
            while(a >= 0 && d <= H){
                if(a == 0){
                    FOR(i, d, H+2) res = res * arr[a][i] % mod;
                    break;
                }
                res = res * arr[a][d] % mod;
                res = res * arr[a][d+1] % mod;
                a = par[a];
                d++;
            }
            cout << res << '\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