Submission #1003680

#TimeUsernameProblemLanguageResultExecution timeMemory
1003680onbertSprinkler (JOI22_sprinkler)C++17
41 / 100
4105 ms178832 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 2e5 + 5, maxN = 8e5 + 5, m = 43; int n, M; vector<int> adj[maxn]; int newid[maxn], d[maxn], fa[maxn], a[maxn]; bool vis[maxn]; pair<int,int> range[maxn][m]; void dfs(int u) { range[u][0] = {newid[u], newid[u]}; if (adj[u].size() == 0) return; for (int v:adj[u]) dfs(v); int sz = adj[u].size(); int l = 0, r = sz - 1; for (int i=1;i<m;i++) { while (l < sz && range[adj[u][l]][i-1].first==-1) l++; while (r >= 0 && range[adj[u][r]][i-1].first==-1) r--; if (l>r) break; range[u][i] = {range[adj[u][l]][i-1].first, range[adj[u][r]][i-1].second}; } } int seg[maxN]; void build(int id, int l, int r) { seg[id] = 1; if (l==r) { seg[id] = a[l]; return; } int mid = (l+r)>>1; build(id<<1, l, mid); build((id<<1)+1, mid+1, r); } void update(int id, int l, int r, int findl, int findr, int val) { if (r<findl || findr<l) return; if (findl<=l && r<=findr) { seg[id] = seg[id] * val % M; return; } int mid = (l+r)>>1; update((id<<1), l, mid, findl, findr, val); update((id<<1)+1, mid+1, r, findl, findr, val); } int qry(int id, int l, int r, int target) { if (r<target || target<l) return 1; if (l==r) return seg[id]; int mid = (l+r)>>1; return (seg[id] * qry(id<<1, l, mid, target) % M) * qry((id<<1)+1, mid+1, r, target) % M; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> M; for (int i=1;i<=n-1;i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int A[n+1]; for (int i=1;i<=n;i++) cin >> A[i]; queue<int> Q; Q.push(1); vis[1] = true, d[1] = 0, fa[1] = -1; int cnter = 0; while (Q.size() > 0) { int u = Q.front(); cnter++; newid[u] = cnter; for (int v:adj[u]) if (!vis[v]) { vis[v] = true, fa[v] = u, d[v] = d[u] + 1; adj[v].erase(find(adj[v].begin(), adj[v].end(), u)); Q.push(v); } Q.pop(); } for (int i=1;i<=n;i++) for (int j=0;j<m;j++) range[i][j] = {-1, -1}; dfs(1); for (int i=1;i<=n;i++) a[newid[i]] = A[i]; build(1, 1, n); int q; cin >> q; while (q--) { int t; cin >> t; if (t==1) { int x, D, w; cin >> x >> D >> w; int v = x; for (int dep = d[x]+D; dep>=d[x]-D && dep >= 0; dep--) { if (fa[v]!=-1 && dep-d[v] + d[x]-d[v] + 2 <= D) v = fa[v]; update(1, 1, n, range[v][dep-d[v]].first, range[v][dep-d[v]].second, w); } } else if (t==2) { int x; cin >> x; cout << qry(1, 1, n, newid[x]) << endl; } // for (int i=1;i<=n;i++) cout << qry(1, 1, n, newid[i]) << " "; cout << endl; } }
#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...