oj.uz

Submission #561342

# Submission time Handle Problem Language Result Execution time Memory
561342 2022-05-12T16:35:09 Z hibiki Sprinkler (JOI22_sprinkler) C++11
0 / 100
 37 ms 70748 KB 
#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()
{
    freopen("01-04.txt","r",stdin);
    // 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

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     freopen("01-04.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d %lld",&n,&mod);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
sprinkler.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%lld",&h[i]);
      |         ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
sprinkler.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
sprinkler.cpp:99:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |             scanf("%d %d %lld",&x,&d,&w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:106:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 70732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 70748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 70748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 70732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 70700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 70732 KB Output isn't correct
2 Halted 0 ms 0 KB -