Submission #588775

#	Time	Username	Problem	Language	Result	Execution time	Memory
588775		balbit	Sprinkler (JOI22_sprinkler)	C++14	0 / 100	1036 ms	253604 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#define pii pair<ll, ll>
#define f first
#define s second

#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 2e5+5;
signed L;
vector<int> rawt[maxn], g[maxn];
int par[maxn];
ll H[maxn];
int ordpos[maxn], dep[maxn];
vector<int> depv[maxn];

ll seg[maxn*4], tg[maxn*4];

inline void push(int o, int l, int r) {
    if (tg[o] != 1) {
        seg[o] *= tg[o]; seg[o] %= L;
        if (l!=r) {
            tg[o*2] = tg[o*2] * tg[o] % L;
            tg[o*2+1] = tg[o*2+1] * tg[o] % L;
        }
        tg[o] = 1;
    }
}

void MO(int L, int R, int v, int o=1, int l=0, int r=maxn-1) {
    push(o,l,r);
    if (l > R || r < L) return;
    if (l >= L && r <= R) {
        tg[o] = tg[o] * v % ::L;
        push(o,l,r); return;
    }
    int mid = (l+r)/2;
    MO(L,R,v,o*2,l,mid); MO(L,R,v,o*2+1,mid+1,r);
    seg[o] = seg[o*2] * seg[o*2+1] % ::L;
}

ll get(int p, int o=1, int l=0, int r=maxn-1) {
    if (l > p || r < p) assert(0);
    push(o,l,r);
    if (l == r) return seg[o];
    int mid = (l+r)/2;
    if (p <= mid) return get(p,o*2,l,mid);
    else return get(p,o*2+1,mid+1,r);
}

ll tomul[maxn][41];

void build(){
    fill(seg, seg+maxn*4, 1);
    fill(tg, tg+maxn*4, 1);
}

void dfs1(int v, int p) {
    par[v] = p;
    depv[dep[v]].pb(v);
    for (int u : rawt[v]) {
        if (u == p) continue;
        g[v].pb(u);
        dep[u] = dep[v] + 1;
        dfs1(u,v);
    }
}

pii rnghere[maxn][41];

void dfs2(int v) {
    fill(rnghere[v], rnghere[v]+41, pii{10000000,-1});
    rnghere[v][0] = {ordpos[v],ordpos[v]};
    for (int u : g[v]) {
        dfs2(u);
        REP(d, 40) {
            if (rnghere[u][d].s != -1) {
                MN(rnghere[v][d+1].f, rnghere[u][d].f);
                MX(rnghere[v][d+1].s, rnghere[u][d].s);
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);

    int n; cin>>n>>L;
    REP(i,n-1) {
        int a,b; cin>>a>>b; --a; --b;
        rawt[a].pb(b);
        rawt[b].pb(a);
    }

    dfs1(0,-1);
    int IT = 0;
    REP(i, maxn) {
        for (int e : depv[i]) {
            bug(e, IT);
            ordpos[e] = IT++;
        }
    }
    build();

    dfs2(0);

    REP(i,n) {
        cin>>H[i];
//        , MO(ordpos[i],ordpos[i],H[i]);
        tomul[i][0] = H[i];
    }

    int q; cin>>q;
    REP(i,n) REP(j,41) tomul[i][j] = 1;
    while (q--) {
        int tp; cin>>tp;
        if (tp == 1) {
            int v, d, w; cin>>v>>d>>w; --v;
            int at = v;
            for (int dp = dep[v] + d; dp >= dep[v] - d; dp--) {
                if (dp < 0 || dp >= maxn || SZ(depv[dp]) == 0) continue;
                while (at != 0 && dep[v] - dep[par[at]] + dp - dep[par[at]] <= d) {
                    at = par[at];
                }
//                pii ha = rnghere[at][dp-dep[at]];
//                if (ha.f == -1) continue;
//                bug(ha.f, ha.s, w);
//                MO(ha.f, ha.s, w);
                (tomul[at][dp-dep[at]] *= w) %= L;
            }
        }else{
            int v; cin>>v; --v;
//            bug(ordpos[v]);
//            cout<<get(ordpos[v])<<endl;
            int dp = dep[v];ll re =  1;
            for (int at = v; at!=-1 && dp-dep[at]<=40; at = par[at]) {
                re = re * tomul[at][dp-dep[at]]; re %= L;
            }
            cout<<re<<endl;
        }

    }

}

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