Submission #792132

#TimeUsernameProblemLanguageResultExecution timeMemory
792132quanlt206Sprinkler (JOI22_sprinkler)C++14
3 / 100
4144 ms702020 KiB
#include<bits/stdc++.h> #define X first #define Y second #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FORD(i, b, a) for (int i = (b); i >= (a); i--) #define REP(i, a, b) for (int i = (a); i < (b); i++) #define MASK(x) (1LL << (x)) #define all(x) begin(x), end(x) using namespace std; typedef long long ll; typedef long double ld; typedef double db; typedef pair<int, int> pii; typedef pair<int, pii> piii; typedef pair<ll, ll> pll; typedef pair<ll, pll> plll; typedef pair<ll, int> pli; typedef pair<ll, pii> plii; template<class A, class B> bool maximize(A& x, B y) { if (x < y) return x = y, true; else return false; } template<class A, class B> bool minimize(A& x, B y) { if (x > y) return x = y, true; else return false; } /* END OF TEMPLATE */ const int N = 2e5 + 7; int n, mod, P[N], pos[N]; ll res[N][50], h[N], res2[N][50]; vector<int> v[N]; struct SegmentTree { struct Node { ll lazy, val; Node() { val = 1; } } st[4 * N]; ll mul(ll a, ll b) { if (b == 0) return 1; ll tmp = mul(a, b / 2); tmp = tmp * tmp % mod; if (b & 1) tmp = tmp * a % mod; return tmp; } void Up(int id, int l, int r) { if (l == r) return ; st[id].val = st[id * 2].val * st[id * 2 + 1].val % mod; } void update(int id, int l, int r, int i, ll x) { if (l > i || r < i) return ; if (l == r) { st[id].val = st[id].val * x % mod; return ; } int mid = (l + r) >> 1; update(id * 2, l, mid, i, x); update(id * 2 + 1, mid + 1, r, i, x); Up(id, l, r); } ll Get(int id, int l, int r, int u, int v) { if (l > v || r < u || l > r) return 1; if (u <= l && r <= v) return st[id].val; int mid = (l + r) >> 1; return Get(id * 2, l, mid, u, v) * Get(id * 2 + 1, mid + 1, r, u, v) % mod; } } st[42]; void dfs(int x, int par) { P[x] = par; for (auto y : v[x]) if (y != par) dfs(y, x); } void firstQuery() { int x, d, w; cin>>x>>d>>w; FOR(j, 0, d) res2[x][j] = res2[x][j] * w % mod; int tmp = 0; while (x != -1 && tmp <= d) { st[d - tmp].update(1, 1, n, pos[x], w); res[x][d - tmp] = res[x][d - tmp] * w % mod; tmp++; x = P[x]; } } void secondQuery() { int x; cin>>x; ll ans = h[x]; int tmp = 1; int last_x = x; // ans = ans * res2[x][0] % mod; FOR(i, 0, 40) ans = ans * res[x][i] % mod; x = P[x]; // cout<<res[2][1]<<"\n"; // cout <<x<<" "<<ans<<"\n"; while (x != -1 && tmp <= 40) { ans = ans * res2[x][tmp] % mod; // cout<<x<<" "<<ans<<"\n"; // ans = ans * res[x][0] % mod; if (tmp < 40) { int t = lower_bound(all(v[x]), last_x) - v[x].begin(); if (t < (int)v[x].size()) { FOR(j, tmp + 1, 40) { ans = ans * st[j].Get(1, 1, n, pos[v[x][0]], pos[v[x][t]] - 1) % mod; ans = ans * st[j].Get(1, 1, n, pos[v[x][t]] + 1, pos[v[x].back()]) % mod; } } // for (auto y : v[x]) // if (y != last_x && y != P[x]) { // FOR(j, 0, 40) // if (j >= tmp + 1) { // ans = ans * res[y][j] % mod; //// cout<<y<<" "<<j<<" "<<res[y][j]<<"\n"; // } // } } // cout<<x<<" "<<ans<<"\n"; // break; last_x = x; x = P[x]; tmp++; } cout<<ans<<"\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>mod; REP(i, 1, n) { int x, y; cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } FOR(i, 1, n) FOR(j, 0, 40) res[i][j] = res2[i][j] = 1; FOR(i, 1, n) cin>>h[i]; dfs(1, -1); FOR(i, 1, n) { vector<int> a; for (auto x : v[i]) if (x != P[i]) a.push_back(x); v[i] = a; sort(all(v[i])); } int cnt = 0; FOR(i, 1, n) for (auto x : v[i]) pos[x] = ++cnt; int Q; cin>>Q; while (Q--) { int type; cin>>type; if (type == 1) firstQuery(); else secondQuery(); } 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...