oj.uz

Submission #561318

# Submission time Handle Problem Language Result Execution time Memory
561318 2022-05-12T16:00:54 Z hibiki Sprinkler (JOI22_sprinkler) C++11
12 / 100
 840 ms 92324 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 || 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70732 KB Output is correct
2 Correct 40 ms 70636 KB Output is correct
3 Correct 41 ms 70660 KB Output is correct
4 Incorrect 33 ms 70760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70740 KB Output is correct
2 Incorrect 742 ms 88220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70740 KB Output is correct
2 Incorrect 742 ms 88220 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 33 ms 70764 KB Output is correct
2 Correct 840 ms 87808 KB Output is correct
3 Correct 797 ms 87932 KB Output is correct
4 Correct 692 ms 91364 KB Output is correct
5 Correct 593 ms 88200 KB Output is correct
6 Correct 438 ms 87780 KB Output is correct
7 Correct 444 ms 88220 KB Output is correct
8 Correct 327 ms 88412 KB Output is correct
9 Correct 782 ms 91212 KB Output is correct
10 Correct 741 ms 92324 KB Output is correct
11 Correct 720 ms 87656 KB Output is correct
12 Correct 682 ms 88272 KB Output is correct
13 Correct 457 ms 88884 KB Output is correct
14 Correct 531 ms 89916 KB Output is correct
15 Correct 31 ms 70740 KB Output is correct
16 Correct 32 ms 70732 KB Output is correct
17 Correct 31 ms 70752 KB Output is correct
18 Correct 32 ms 70740 KB Output is correct
19 Correct 33 ms 70740 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70716 KB Output is correct
2 Correct 832 ms 89892 KB Output is correct
3 Incorrect 800 ms 87484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70732 KB Output is correct
2 Correct 40 ms 70636 KB Output is correct
3 Correct 41 ms 70660 KB Output is correct
4 Incorrect 33 ms 70760 KB Output isn't correct
5 Halted 0 ms 0 KB -