제출 #588814

#제출 시각아이디문제언어결과실행 시간메모리
588814SeDunionSprinkler (JOI22_sprinkler)C++17
100 / 100
683 ms101904 KiB
#include<iostream> #include<vector> using namespace std; using ll = long long; const int N = 5e5 + 123; const int LOG = 20; const int D = 45; ll h[N], q[N][D]; int n, L; void mult(ll &a, ll b) { a *= b; a %= L; } vector<int>g[N]; int pr[N]; void dfs(int v) { for (int to : g[v]) if (to != pr[v]) { pr[to] = v; dfs(to); } } ll binpow(ll a, ll b) { ll r = 1; while (b) { if (b & 1) r = r * a % L; a = a * a % L; b >>= 1; } return r; } ll ih[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> L; for (int i = 1 ; i < n ; ++ i) { int a, b; cin >> a >> b; g[a].emplace_back(b); g[b].emplace_back(a); } int m = n; g[1].emplace_back(++m); g[m].emplace_back(1); for (int i = 0 ; i < 44 ; ++ i) { int x = m, y = m + 1; ++m; g[x].emplace_back(y); g[y].emplace_back(x); } dfs(m); for (int i = 1 ; i <= m ; ++ i) { for (int j = 0 ; j <= 43 ; ++ j) { q[i][j] = 1; } } for (int i = 1 ; i <= n ; ++ i) { cin >> ih[i]; } int qq; cin >> qq; while (qq--) { int t, x, d, w; cin >> t; if (t == 1) { cin >> x >> d >> w; for (int i = d ; i >= 0 ; -- i) { mult(q[x][i], w); // cout << x << " upd\n"; x = pr[x]; } } else { cin >> x; ll ans = ih[x]; for (int i = 0 ; i <= 41 ; ++ i) { mult(ans, q[x][i]); mult(ans, q[x][i+1]); // cout << x << " get\n"; x = pr[x]; } cout << ans << "\n"; //cout << ret*binpow(2, ans) % L << "\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...