Submission #999553

#	Time	Username	Problem	Language	Result	Execution time	Memory
999553		Saul0906	Sprinkler (JOI22_sprinkler)	C++14	21 / 100	1179 ms	116040 KiB

sprinkler

#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];
        if(!x.fi && d==2) H[u]=(H[u]*w)%L;
        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};
        }
        ST[lvl[u]].update(pos[u]+(d==2),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;
                }
        }
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:125:15: warning: unused variable 'm' [-Wunused-variable]
  125 |         ll n, m, u, v;
      |               ^

• Subtask 1: 0 / 3
• Subtask 2: 9 / 9
• Subtask 3: 0 / 29
• Subtask 4: 12 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17