Submission #561343

#	Time	Username	Problem	Language	Result	Execution time	Memory
561343		hibiki	Sprinkler (JOI22_sprinkler)	C++11	100 / 100	1180 ms	94760 KiB

sprinkler

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

#define pb push_back
#define f first
#define s second

int n,q,fa[200005];
long long mod,h[200005];
long long mul[200005][42];
vector<int> v[200005];

void dfs(int nw,int pre)
{
    fa[nw] = pre;
    for(auto go: v[nw])
    {
        if(go == pre) continue;

        dfs(go,nw);
    }
}

void update(int nw,int left,long long w)
{
    mul[nw][left] *= w;
    mul[nw][left] %= mod;

    if(left == 0)
        return ;

    if(fa[nw] == -1)
    {
        for(int i = left -1; i >= 0; i--)
        {
            mul[nw][i] *= w;
            mul[nw][i] %= mod;
        }
        return ;
    }

    mul[nw][left - 1] *= w;
    mul[nw][left - 1] %= mod;

    update(fa[nw],left - 1,w);
}

long long query(int nw,int dis)
{
    long long ret = 1ll;

    ret *= mul[nw][dis];
    ret %= mod;

    if(dis == 41 || fa[nw] == -1)
        return ret;

    long long pre = query(fa[nw],dis + 1);
    pre %= mod;

    ret *= pre;
    ret %= mod;

    return ret;
}

int main()
{
    // initialize
    for(int i = 0; i < 200005; i++)
        for(int j = 0; j < 42; j++)
            mul[i][j] = 1ll;

    // input
    scanf("%d %lld",&n,&mod);
    for(int i = 0; i < n - 1; i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        v[a].pb(b);
        v[b].pb(a);
    }
    for(int i = 1; i <= n; i++)
        scanf("%lld",&h[i]);

    dfs(1,-1);

    scanf("%d",&q);
    for(int i = 0; i < q; i++)
    {
        int t;
        scanf("%d",&t);

        if(t == 1)
        {
            int x,d;
            long long w;
            scanf("%d %d %lld",&x,&d,&w);
            w %= mod;
            update(x,d,w);
        }
        else
        {
            int x;
            scanf("%d",&x);
            long long ans = h[x] * query(x,0);
            ans %= mod;
            printf("%lld\n",ans);
        }
    }

    return 0;
}

/*
16 12
1 2
2 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
8 12
10 13
10 14
10 15
11 16
2
1
1
1
2
1
1
2
1
1
1
1
1
1
1
1
*/

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%d %lld",&n,&mod);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
sprinkler.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%lld",&h[i]);
      |         ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
sprinkler.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
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 %lld",&x,&d,&w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |             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