Submission #925909

#	Time	Username	Problem	Language	Result	Execution time	Memory
925909		andrei_boaca	Sprinkler (JOI22_sprinkler)	C++17	3 / 100	3829 ms	1048576 KiB

sprinkler

#include <bits/stdc++.h>

using namespace std;
int n,mod,h[200005],root;
vector<int> muchii[200005];
vector<int> kids[200005];
int d1[200005],dp[21][200005],in[200005],out[200005],timp;
int use[200005],parent[200005],par[200005];
int nr[200005],where[200005];
int add[200005][41];
vector<int> aib[2][200005][41];   /// 0 -> pref, 1 -> suf
bool isancestor(int a,int b)
{
    return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b)
{
    if(d1[a]>d1[b])
        swap(a,b);
    if(isancestor(a,b))
        return a;
    for(int i=18;i>=0;i--)
        if(dp[i][a]!=0&&!isancestor(dp[i][a],b))
            a=dp[i][a];
    return dp[0][a];
}
int dist(int a,int b)
{
    int lca=LCA(a,b);
    return d1[a]+d1[b]-2*d1[lca];
}
void build(int nod)
{
    timp++;
    in[nod]=timp;
    for(int i=1;i<=20;i++)
        dp[i][nod]=dp[i-1][dp[i-1][nod]];
    for(int i:muchii[nod])
        if(i!=dp[0][nod])
        {
            dp[0][i]=nod;
            d1[i]=d1[nod]+1;
            build(i);
        }
    out[nod]=timp;
}
void dfs1(int nod)
{
    nr[nod]=1;
    for(int i:muchii[nod])
        if(!use[i]&&i!=par[nod])
        {
            par[i]=nod;
            dfs1(i);
            nr[nod]+=nr[i];
        }
}
int centroid(int nod)
{
    par[nod]=0;
    dfs1(nod);
    int lg=nr[nod];
    int r=nod;
    while(true)
    {
        bool bad=0;
        for(int i:muchii[r])
            if(!use[i]&&par[i]==r&&nr[i]>lg/2)
            {
                bad=1;
                par[r]=i;
                par[i]=0;
                nr[r]-=nr[i];
                nr[i]+=nr[r];
                r=i;
                break;
            }
        if(!bad)
            break;
    }
    use[r]=1;
    for(int i:muchii[r])
        if(!use[i])
        {
            int x=centroid(i);
            kids[r].push_back(x);
        }
    return r;
}
void dfs(int nod)
{
    int cnt=0;
    for(int i:kids[nod])
    {
        cnt++;
        where[i]=cnt;
        par[i]=nod;
        dfs(i);
    }
    int lg=kids[nod].size();
    for(int i=0;i<=1;i++)
        for(int j=0;j<=40;j++)
            for(int k=0;k<=lg;k++)
                aib[i][nod][j].push_back(1);
}
int lsb(int x)
{
    return x&(-x);
}
void update(int ind,int cur,int p1,int p2,int val)
{
    int lg=kids[cur].size();
    for(int i=p1;i<=40;i+=lsb(i))
        for(int j=p2;j<=lg;j+=lsb(j))
            aib[ind][cur][i][j]=(1LL*aib[ind][cur][i][j]*val)%mod;
}
int query(int ind,int cur,int p1,int p2)
{
    int rez=1;
    for(int i=p1;i>=1;i-=lsb(i))
        for(int j=p2;j>=1;j-=lsb(j))
            rez=(1LL*rez*aib[ind][cur][i][j])%mod;
    return rez;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>mod;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        cin>>h[i];
    d1[1]=0;
    build(1);
    root=centroid(1);
    par[root]=0;
    dfs(root);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=40;j++)
            add[i][j]=1;
    int q;
    cin>>q;
    while(q--)
    {
        int tip;
        cin>>tip;
        if(tip==1)
        {
            int nod,d,val;
            cin>>nod>>d>>val;
            for(int i=1;i<=d;i++)
                add[nod][i]=(1LL*add[nod][i]*val)%mod;
            int cur=nod;
            int badind=0;
            while(cur!=0)
            {
                int dmax=d-dist(nod,cur);
                if(dmax>=0)
                    h[cur]=(1LL*h[cur]*val)%mod;
                if(dmax>0&&badind!=0)
                {
                    int lg=kids[cur].size();
                    update(1,cur,40-dmax+1,badind+1,val);
                    update(0,cur,40-dmax+1,lg-badind+2,val);
                }
                badind=where[cur];
                cur=par[cur];
            }
        }
        if(tip==2)
        {
            int nod;
            cin>>nod;
            int ans=h[nod];
            int badind=where[nod];
            int cur=par[nod];
            while(cur!=0)
            {
                int d=dist(nod,cur);
                if(d<=40)
                {
                    int lg=kids[cur].size();
                    ans=(1LL*ans*add[cur][d])%mod;
                    int val=query(1,cur,40-d+1,badind);
                    ans=(1LL*ans*val)%mod;
                    val=query(0,cur,40-d+1,lg-badind+1);
                    ans=(1LL*ans*val)%mod;
                }
                badind=where[cur];
                cur=par[cur];
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}

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