Submission #561318

#	Time	Username	Problem	Language	Result	Execution time	Memory
561318		hibiki	Sprinkler (JOI22_sprinkler)	C++11	12 / 100	840 ms	92324 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 %= mod;

    if(left == 0 || fa[nw] == -1)
        return ;

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

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

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

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

    if(fa[nw] == -1)
    {
        for(int i = dis + 1; i < 42; i++)
            ret *= mul[nw][i] %= mod;
        return ret;
    }

    if(dis == 41)
        return ret;

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

    ret *= pre %= 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("%d",&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);
            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;
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:76:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   76 |         scanf("%d",&h[i]);
      |                ~^  ~~~~~
      |                 |  |
      |                 |  long long int*
      |                 int*
      |                %lld
sprinkler.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d %lld",&n,&mod);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
sprinkler.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d",&h[i]);
      |         ~~~~~^~~~~~~~~~~~
sprinkler.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
sprinkler.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
sprinkler.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |             scanf("%d %d %lld",&x,&d,&w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~

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