Submission #1207984

#TimeUsernameProblemLanguageResultExecution timeMemory
1207984HanksburgerSprinkler (JOI22_sprinkler)C++20
41 / 100
4082 ms210144 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct node { node *lc, *rc; int l, r, val; node(int l, int r) : lc(0), rc(0), l(l), r(r), val(1) {} } *root; int mn[200005][50], mx[200005][50], par[200005], mp[200005], a[200005], n, l, Q, t; vector<int> adj[200005]; queue<int> q; void build(node *i) { if (i->l==i->r) { i->val=a[mp[i->l]]; return; } int mid=(i->l+i->r)/2; build(i->lc=new node(i->l, mid)); build(i->rc=new node(mid+1, i->r)); } void update(node *i, int ql, int qr, int x) { if (ql<=i->l && i->r<=qr) { i->val=i->val*x%l; return; } int mid=(i->l+i->r)/2; if (i->l<=qr && ql<=mid) update(i->lc, ql, qr, x); if (mid<qr && ql<=i->r) update(i->rc, ql, qr, x); } int query(node *i, int x) { if (i->l==i->r) return i->val; int mid=(i->l+i->r)/2; if (x<=mid) return i->val*query(i->lc, x)%l; else return i->val*query(i->rc, x)%l; } void dfs(int u) { for (int i=1; i<50; i++) mn[u][i]=1e9; for (int v:adj[u]) { if (v==par[u]) continue; dfs(v); for (int i=1; i<50; i++) { mn[u][i]=min(mn[u][i], mn[v][i-1]); mx[u][i]=max(mx[u][i], mx[v][i-1]); } } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> l; for (int i=1; i<n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for (int i=1; i<=n; i++) cin >> a[i]; q.push(1); while (!q.empty()) { int u=q.front(); q.pop(); mn[u][0]=mx[u][0]=++t; mp[t]=u; for (int v:adj[u]) { if (v==par[u]) continue; par[v]=u; q.push(v); } } dfs(1); build(root=new node(1, n)); cin >> Q; for (int i=1; i<=Q; i++) { int t; cin >> t; if (t==1) { int x, d, w; cin >> x >> d >> w; for (int j=d; j>=0; j--) { if (mn[x][j]<=mx[x][j]) update(root, mn[x][j], mx[x][j], w); if (j && mn[x][j-1]<=mx[x][j-1]) update(root, mn[x][j-1], mx[x][j-1], w); if (x==1) { for (int k=j-2; k>=0; k--) if (mn[x][k]<=mx[x][k]) update(root, mn[x][k], mx[x][k], w); break; } x=par[x]; } } else { int x; cin >> x; cout << query(root, mn[x][0]) << '\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...