Submission #1208344

#TimeUsernameProblemLanguageResultExecution timeMemory
1208344siewjhSprinkler (JOI22_sprinkler)C++20
100 / 100
503 ms85844 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 200005; vector<int> adj[MAXN]; int p[MAXN]; ll mmv[MAXN][41]; void dfs(int x, int par){ p[x] = par; for (int nn : adj[x]) if (nn != par) dfs(nn, x); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int nodes; ll mod; cin >> nodes >> mod; for (int i = 1; i < nodes; i++){ int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, -1); vector<ll> hv(nodes + 1); for (int i = 1; i <= nodes; i++) cin >> hv[i]; for (int i = 1; i <= nodes; i++) for (int d = 0; d <= 40; d++) mmv[i][d] = 1; int queries; cin >> queries; for (int q = 0; q < queries; q++){ int op; cin >> op; if (op == 1){ int x, d; ll mult; cin >> x >> d >> mult; for (int rem = d; rem >= 0; rem--, x = p[x]){ if (p[x] == -1){ for (int i = rem; i >= 0; i--) mmv[x][i] = mmv[x][i] * mult % mod; break; } mmv[x][rem] = mmv[x][rem] * mult % mod; if (rem) mmv[x][rem - 1] = mmv[x][rem - 1] * mult % mod; } } else{ int x; cin >> x; ll ans = hv[x]; for (int d = 0; d <= 40 && x != -1; d++, x = p[x]) ans = ans * mmv[x][d] % mod; cout << ans << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...