oj.uz

Submission #561336

# Submission time Handle Problem Language Result Execution time Memory
561336 2022-05-12T16:30:52 Z hibiki Sprinkler (JOI22_sprinkler) C++11
12 / 100
 968 ms 87520 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 %= mod;

    if(left == 0)
        return ;

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

        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(dis == 41 || fa[nw] == -1)
        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("%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);
            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:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d %lld",&n,&mod);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
sprinkler.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%lld",&h[i]);
      |         ~~~~~^~~~~~~~~~~~~~
sprinkler.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
sprinkler.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%d",&t);
      |         ~~~~~^~~~~~~~~
sprinkler.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |             scanf("%d %d %lld",&x,&d,&w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70720 KB Output is correct
2 Correct 34 ms 70740 KB Output is correct
3 Correct 33 ms 70688 KB Output is correct
4 Incorrect 33 ms 70748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 70676 KB Output is correct
2 Incorrect 786 ms 84224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 70676 KB Output is correct
2 Incorrect 786 ms 84224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70740 KB Output is correct
2 Correct 953 ms 86788 KB Output is correct
3 Correct 933 ms 84852 KB Output is correct
4 Correct 856 ms 84656 KB Output is correct
5 Correct 656 ms 80884 KB Output is correct
6 Correct 431 ms 81156 KB Output is correct
7 Correct 455 ms 81096 KB Output is correct
8 Correct 336 ms 81544 KB Output is correct
9 Correct 845 ms 84596 KB Output is correct
10 Correct 803 ms 84696 KB Output is correct
11 Correct 838 ms 81276 KB Output is correct
12 Correct 761 ms 80596 KB Output is correct
13 Correct 510 ms 81548 KB Output is correct
14 Correct 521 ms 81856 KB Output is correct
15 Correct 38 ms 70680 KB Output is correct
16 Correct 37 ms 70748 KB Output is correct
17 Correct 38 ms 70744 KB Output is correct
18 Correct 36 ms 70668 KB Output is correct
19 Correct 47 ms 70724 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 70728 KB Output is correct
2 Correct 968 ms 87520 KB Output is correct
3 Incorrect 961 ms 84224 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70720 KB Output is correct
2 Correct 34 ms 70740 KB Output is correct
3 Correct 33 ms 70688 KB Output is correct
4 Incorrect 33 ms 70748 KB Output isn't correct
5 Halted 0 ms 0 KB -