Submission #547314

#	Time	Username	Problem	Language	Result	Execution time	Memory
547314		ToroTN	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	1043 ms	87360 KiB

sprinkler

#include<bits/stdc++.h>
using namespace std;
int n,l,u_i,v_i,h[200005],t,op,x,d,w,u,p[200005],arr[45],ed,kk,bruh;
int prime[200005],phi;
long long power[35],inv,cnt,dp[200005][45];
vector<int> v[200005],g;
queue<int> q;
int main()
{
    scanf("%d%d",&n,&l);
    bruh=l;
    phi=l;
    for(int i=2;i<=100000;i++)
    {
        prime[i]=1;
    }
    for(int i=2;i<=100000;i++)
    {
        if(prime[i]==1)
        {
            for(int j=2;i*j<=100000;j++)
            {
                prime[i*j]=0;
            }
        }
    }
    for(int i=2;i<=100000;i++)
    {
        if(prime[i]==1)
        {
            if(l%i==0)
            {
                phi/=i;
                phi*=(i-1);
                while(1)
                {
                    if(bruh%i==0)
                    {
                        bruh/=i;
                    }else
                    {
                        break;
                    }
                }
            }
        }
    }
    if(bruh!=1)
    {
        phi/=bruh;
        phi*=(bruh-1);
    }
    u=phi-1;
    for(int i=0;i<=30;i++)
    {
        g.push_back(u%2);
        u/=2;
    }
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u_i,&v_i);
        v[u_i].push_back(v_i);
        v[v_i].push_back(u_i);
    }
    memset(p,-1,sizeof p);
    p[1]=0;
    q.push(1);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        for(int i=0;i<v[u].size();i++)
        {
            if(p[v[u][i]]==-1)
            {
                p[v[u][i]]=u;
                q.push(v[u][i]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&h[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=40;j++)
        {
            dp[i][j]=1;
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&x,&d,&w);
            power[0]=w;
            for(int i=1;i<=30;i++)
            {
                power[i]=power[i-1]*power[i-1];
                power[i]%=l;
            }
            inv=1;
            for(int i=0;i<=30;i++)
            {
                if(g[i]==1)
                {
                    inv*=power[i];
                    inv%=l;
                }
            }
            u=x;
            for(int i=d;i>=0;i--)
            {
                arr[i]=u;
                ed=i;
                u=p[u];
                if(u==0)
                {
                    break;
                }
            }
            for(int i=d;i>=ed;i--)
            {
                /*dp[arr[i]][i]*=w;
                dp[arr[i]][i]%=l;
                if(i-1>=0&&i+1<=d)
                {
                    dp[arr[i+1]][i-1]*=inv;
                    dp[arr[i+1]][i-1]%=l;
                }*/
                if(i!=ed)
                {
                    dp[arr[i]][i]*=w;
                    dp[arr[i]][i]%=l;
                    dp[arr[i]][i-1]*=w;
                    dp[arr[i]][i-1]%=l;
                }else
                {
                    for(int j=0;j<=i;j++)
                    {
                        dp[arr[i]][j]*=w;
                        dp[arr[i]][j]%=l;
                    }
                }
            }
        }else
        {
            scanf("%d",&x);
            u=x;
            cnt=h[x];
            for(int i=0;i<=40;i++)
            {
                /*for(int j=i;j<=40;j++)
                {
                    cnt*=dp[u][j];
                    cnt%=l;
                }*/
                cnt*=dp[u][i];
                cnt%=l;
                u=p[u];
                if(u==0)
                {
                    break;
                }
            }
            printf("%lld\n",cnt);
        }
    }
}
/*
4 7
1 2
2 3
3 4
1
1
1
1
11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4
*/

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int i=0;i<v[u].size();i++)
      |                     ~^~~~~~~~~~~~
sprinkler.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d%d",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d%d",&u_i,&v_i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
sprinkler.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d",&h[i]);
      |         ~~~~~^~~~~~~~~~~~
sprinkler.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d",&t);
      |     ~~~~~^~~~~~~~~
sprinkler.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         scanf("%d",&op);
      |         ~~~~~^~~~~~~~~~
sprinkler.cpp:98:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |             scanf("%d%d%d",&x,&d,&w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:151:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~

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