Submission #1184037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184037		browntoad	Sprinkler (JOI22_sprinkler)	C++20	54 / 100	2235 ms	333344 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
// #define int ll
#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 RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const ll maxn = 2e5+5;

int n, mod, q;
int phi;
vector<int> g[maxn];
vector<int> H(maxn);

ll pw(ll a, ll p){
    ll ret = 1;
    while(p > 0){
        if (p & 1){
            ret *= a;
            ret %= mod;
        }
        a *= a;
        a %= mod;
        p >>= 1;
    }
    return ret;
}
ll inv(ll a){
    return pw(a, phi-1);
}

const int mxdis = 40;

int eptr = 0;
int Bv[mxdis+2][10][2*maxn];
int Av[mxdis+2][2*maxn];
int Btot[mxdis+2][10][maxn];
int Atot[mxdis+2][maxn];

void Bvupd(int pos, int b, int c, int val){
    pos = mxdis-pos+1;
    while(pos <= mxdis+1){
        Bv[pos][b][c] += val;
        pos += (pos&-pos);
    }
}
int Bvque(int pos, int b, int c){
    pos = mxdis-pos+1;
    int ret = 0;
    while(pos > 0){
        ret += Bv[pos][b][c];
        pos -= (pos&-pos);
    }
    return ret;
}
void Btotupd(int pos, int b, int c, int val){
    pos = mxdis-pos+1;
    while(pos <= mxdis+1){
        Btot[pos][b][c] += val;
        pos += (pos&-pos);
    }
}
int Btotque(int pos, int b, int c){
    pos = mxdis-pos+1;
    int ret = 0;
    while(pos > 0){
        ret += Btot[pos][b][c];
        pos -= (pos&-pos);
    }
    return ret;
}
void Avupd(int pos, int b, int val){
    pos = mxdis-pos+1;
    while(pos <= mxdis+1){
        Av[pos][b] = ((ll)(Av[pos][b]) * val)%mod;
        pos += (pos&-pos);
    }
}
int Avque(int pos, int b){
    pos = mxdis-pos+1;
    int ret = 1;
    while(pos > 0){
        ret = ((ll)(ret) * Av[pos][b])%mod;
        pos -= (pos&-pos);
    }
    return ret;
}
void Atotupd(int pos, int b, int val){
    pos = mxdis-pos+1;
    while(pos <= mxdis+1){
        Atot[pos][b] = ((ll)(Atot[pos][b]) * val)%mod;
        pos += (pos&-pos);
    }
}
int Atotque(int pos, int b){
    pos = mxdis-pos+1;
    int ret = 1;
    while(pos > 0){
        ret = ((ll)(ret) * Atot[pos][b])%mod;
        pos -= (pos&-pos);
    }
    return ret;
}

// centroid decomposition
vector<bool> isrem(maxn); // removed?
vector<int> preeid[maxn], precent[maxn], dis[maxn]; // eid connecting previous centroid - this centroid, previous centroid. last precent is itself
vector<int> sz(maxn); 


int find_sz(int u, int pre){
    sz[u] = 1;
    for (auto v:g[u]){
        if (v != pre && !isrem[v]) sz[u] += find_sz(v, u);
    }
    return sz[u];
}
int find_centroid(int u, int expsz, int pre){
    for (auto v:g[u]){
        if (!isrem[v] && v != pre && sz[v]*2 > expsz){
            return find_centroid(v, expsz, u);
        }
    }    
    return u;
}

void centupd(int u, int peid, int pecent, int cd, int pre){
    preeid[u].pb(peid);
    precent[u].pb(pecent);
    dis[u].pb(cd);
    for (auto v:g[u]){
        if (!isrem[v] && v != pre){
            centupd(v, peid, pecent, cd+1, u);
        }
    }

}
void decomposition(int u){
    int cent = find_centroid(u, find_sz(u, -1), -1);
    isrem[cent] = 1;
    precent[cent].pb(cent);
    for (auto v:g[cent]){
        if (!isrem[v]){
            centupd(v, eptr++, cent, 1, cent);
            decomposition(v);
        }
    }
}

vector<int> sieve(maxn), prim;
vector<int> specp;

void modify(int U, int D, int W){
    ll A = 1;
    vector<int> B(SZ(specp));
    if (W == 0){
        B[0] = 1;
    }
    else{
        REP1(i, SZ(specp)-1){
            while(W%specp[i] == 0){
                B[i]++;
                W /= specp[i];
            }
        }
        A = W;
    }
    REP(i, SZ(precent[U])){
        int u = precent[U][i]; // centroid id
        if (u == U){
            Atotupd(D, u, A);
            REP(k, SZ(specp)) Btotupd(D, k, u, B[k]); 
        }
        else{
            int eid = preeid[U][i], dd = D-dis[U][i];
            if (dd < 0) continue;

            Atotupd(dd, u, A);
            Avupd(dd, eid, A);
            REP(k, SZ(specp)){
                Btotupd(dd, k, u, B[k]);
                Bvupd(dd, k, eid, B[k]);
            }
        }
    }

}
int query(int U){
    ll A = 1, Ainv = 1;
    vector<int> B(SZ(specp));
    REP(i, SZ(precent[U])){
        int u = precent[U][i];
        if (u == U){
            A = (A * Atotque(0, u))%mod;
            REP(p, SZ(specp)) B[p] += Btotque(0, p, u);
        }
        else{
            int eid = preeid[U][i], dd = dis[U][i];
            if (dd > mxdis) continue;
            A = (A * Atotque(dd, u))%mod;
            Ainv = (Ainv * Avque(dd, eid))%mod;
            REP(p, SZ(specp)){
                B[p] += Btotque(dd, p, u);
                B[p] -= Bvque(dd, p, eid);
            }
            
        }
    }
    if (B[0] > 0) return 0;
    A *= inv(Ainv);
    A %= mod;
    REP1(i, SZ(specp)-1){
        A = (A * pw(specp[i], B[i]) % mod);
    }
    A = (A * H[U])%mod;
    return A;
}

signed main(){
    IOS();
    cin>>n>>mod;
    specp.pb(0);
    int tmod = mod;
    FOR(i, 2, maxn){
        if (!sieve[i]) prim.pb(i);
        for (int j = i+i; j < maxn; j += i) sieve[j] = 1;
    }
    phi = mod;
    for (auto v:prim){
        if (tmod%v == 0){
            while(tmod%v == 0) tmod/=v;
            specp.pb(v);
        }
    }
    if (tmod > 1) specp.pb(tmod);
    for (auto p:specp){
        if (p > 0) phi = ((ll)(p-1) * phi)/p;
    }
    specp.clear(); specp.pb(0); specp.pb(2);

    REP(i, mxdis+2){
        REP(j, maxn){
            Atot[i][j] = 1;
        }
        REP(j, 2*maxn){
            Av[i][j] = 1;
        }
    }

    REP(i, n-1){
        int u, v; cin>>u>>v;
        g[u].pb(v); g[v].pb(u);
    }
    REP1(i, n) cin>>H[i];
    decomposition(1);

    cin>>q;
    REP(i, q){
        int t; cin>>t;
        if (t == 1){
            int a, b, c; cin>>a>>b>>c;
            modify(a, b, c);
        }
        else{
            int x; cin>>x;
            cout<<query(x)<<endl;
        }
    }
}

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