제출 #999546

#제출 시각아이디문제언어결과실행 시간메모리
999546Saul0906Sprinkler (JOI22_sprinkler)C++14
9 / 100
1308 ms126932 KiB
#include <bits/stdc++.h> #define rep(a,b,c) for(int a=b; a<c; a++) #define pb push_back #define pll pair<ll, ll> #define ll long long #define fi first #define se second #define pb push_back #define repa(a,b) for(auto a:b) #define endl "\n" using namespace std; const int lim=2e5+5; vector<int> adj[lim]; int sz[lim], h[lim][20], pos[lim], sum[20], lvl[lim], mx[lim]; pll par[lim]; ll L, H[lim]; bool vis[lim], vis2[lim][20]; struct segtree { int n; vector<ll> tree; segtree() { n = lim; tree.assign(2 * n, 1); } void update(int l, int r, ll value) { for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) tree[l] = (tree[l] * value) % L, l++; if (r & 1) --r, tree[r] = (tree[r] * value) % L; } } ll query(int pos) { ll res = 1; for (pos += n; pos > 0; pos >>= 1) { res = (res * tree[pos]) % L; } return res; } } ST[20]; void sztree(int u, int p=0){ sz[u]=1; repa(v,adj[u]){ if(v==p || vis[v]) continue; sztree(v,u); sz[u]+=sz[v]; } } void dis(int u, int l){ int x=0, d=0; queue<int> q; q.push(u); q.push(0); h[u][l]=0; vis2[u][l]=true; while(q.size()){ x=q.front(); q.pop(); d=q.front(); q.pop(); repa(y,adj[x]){ if(!vis2[y][l] && !vis[y]){ h[y][lvl[u]]=d+1; q.push(y); q.push(d+1); vis2[y][l]=true; } } } pos[u]=sum[l]; sum[l]+=d+1; mx[u]=d; } pll find_centroid(int u, int p, int r){ repa(v,adj[u]){ if(v==p || vis[v]) continue; if(sz[v]>sz[r]/2){ pll x=find_centroid(v,u,r); return {x.fi,x.se+1}; } } return {u,0}; } void centroid(int u, int p=0, int l=0){ sztree(u); pll x=find_centroid(u,p,u); u=x.fi; lvl[u]=l; par[u]={p,x.se+1}; dis(u,l); vis[u]=true; repa(v,adj[u]) if(!vis[v]) centroid(v,u,l+1); } void update(int u, int d, ll w){ pll x=par[u]; while(x.fi){ if(h[u][lvl[x.fi]]<=d) ST[lvl[x.fi]].update(pos[x.fi],pos[x.fi]+min(d-h[u][lvl[x.fi]],mx[x.fi]),w); x={par[x.fi].fi,par[x.fi].se+x.se}; } if(d<=1) ST[lvl[u]].update(pos[u],pos[u]+min(d,mx[u]),w); else if(mx[u]) ST[lvl[u]].update(pos[u]+1,pos[u]+min(d,mx[u]),w); } ll query(int u){ pll x={u,0}; ll ans=H[u]; while(x.fi){ ans*=ST[lvl[x.fi]].query(pos[x.fi]+h[u][lvl[x.fi]]); ans%=L; x=par[x.fi]; } return ans; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n, m, u, v; cin>>n>>L; rep(i,1,n){ cin>>u>>v; adj[u].pb(v); adj[v].pb(u); } rep(i,0,n) cin>>H[i+1]; centroid(u); int q; cin>>q; while(q--){ ll t, x, d, w; cin>>t; if(t&1){ cin>>x>>d>>w; update(x,d,w); }else{ cin>>x; cout<<query(x)<<endl; } } }

컴파일 시 표준 에러 (stderr) 메시지

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:125:8: warning: unused variable 'm' [-Wunused-variable]
  125 |  ll n, m, u, v;
      |        ^
#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...