Submission #1245941

#TimeUsernameProblemLanguageResultExecution timeMemory
1245941tapilyocaSprinkler (JOI22_sprinkler)C++20
100 / 100
807 ms96008 KiB
/*********************************************** * auth: tapilyoca * * date: 07/22/2025 at 23:51:49 * * dots: https://github.com/tapilyoca/dotilyoca * ***********************************************/ #include <bits/stdc++.h> using namespace std; template<typename T> using vec = vector<T>; using ll = long long; using vll = vec<ll>; using vvll = vec<vll>; using pll = pair<ll,ll>; using str = string; #define pb push_back #define dbg(x) if(1) cerr << #x << ": " << x << endl; /***********************************************/ ll MOD, n; vll up; vvll adj, mult; void dfs(ll u, ll p) { up[u] = p; for(ll &v : adj[u]) if(v != p) dfs(v,u); } void solve() { cin >> n >> MOD; adj.resize(n); up.resize(n); mult.assign(n,vll(41,1)); for(int i = 0; i < n-1; i++) { ll u, v; cin >> u >> v; u--; v--; adj[u].pb(v); adj[v].pb(u); } dfs(0,-1); for(int i = 0; i < n; i++) cin >> mult[i][0]; ll q; cin >> q; // cerr << "Dfs done" << endl; while(q--) { // cerr << mult[0][0] << " " << mult[1][0] << " " << mult[2][0] << " " << mult[3][0] << endl; ll type; cin >> type; if(type == 1) { ll x, d, w; cin >> x >> d >> w; x--; // cerr << "Upd on " << x << " " << d << " " << w << endl; while(d >= 0) { if(up[x] == -1) { for(int i = 0; i <= d; i++) mult[x][i] = (mult[x][i] * w) % MOD; break; } mult[x][d] = (mult[x][d] * w) % MOD; if(d) mult[x][d-1] = (mult[x][d-1] * w) % MOD; x = up[x]; d--; } } else { ll x, ans = 1, at = 0; cin >> x; x--; // cerr << "qry " << x << endl; while(x != -1 and at <= 40) { ans = (ans * mult[x][at]) % MOD; x = up[x]; at++; } cout << ans << endl; } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int t = 1; while(t--) { solve(); } return 0; }
#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...