oj.uz

Submission #568461

# Submission time Handle Problem Language Result Execution time Memory
568461 2022-05-25T13:37:11 Z dantoh000 Sprinkler (JOI22_sprinkler) C++14
0 / 100
 753 ms 98084 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,l,q;
vector<int> G[200005];
int p[200005];
int h[200005][50];
void dfs(int u){
    for (auto v : G[u]){
        if (v == p[u]) continue;
        p[v] = u;
        dfs(v);
    }
}
void up(int x, int d, int w){
    ///printf("update %lld of %lld\n",d,x);
    int cur = x;
    while (cur != 1 && d >= 0){
        ///printf("%lld child of %lld\n",d,cur);
        ///printf("%lld child of %lld\n",d-1,cur);
        h[cur][d] = (h[cur][d]*w)%l;
        if (d) h[cur][d-1] = (h[cur][d-1]*w)%l;
        cur = p[cur];
        d--;
    }
    if (cur == 1){
        while (d >= 0){
            ///printf("%lld child of %lld\n",d,1);
            h[1][d] = (h[1][d]*w)%l;
            d--;
        }
    }
}
int qu(int x){
    ///printf("query %lld\n",x);
    int cur = x;
    int d = 0;
    int ret = 1;
    for (d = 0; d <= 40 && cur != 1; d++){
        ///printf("adding %lld child of %lld\n",d,cur);
        ret = (ret*h[cur][d])%l;
        cur = p[cur];
    }
    ///printf("adding %lld child of %lld\n",d,1);
    if (cur == 1) ret = (ret*h[1][d])%l;
    return ret;
}
main(){
    scanf("%lld%lld",&n,&l);
    for (int i = 0,a,b; i < n-1; i++){
        scanf("%lld%lld",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    p[1] = -1;
    dfs(1);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= 40; j++) h[i][j] = 1;
    for (int i = 1; i <= n; i++){
        scanf("%lld",&h[i][0]);
    }
    scanf("%lld",&q);
    for (int i = 0,t; i < q; i++){
        scanf("%lld",&t);
        if (t == 1){
            int x,d,w;
            scanf("%lld%lld%lld",&x,&d,&w);
            up(x,d,w);
        }
        else {
            int x;
            scanf("%lld",&x);
            printf("%lld\n",qu(x));
        }
    }

}

Compilation message

sprinkler.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main(){
      | ^~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%lld%lld",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
sprinkler.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%lld%lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
sprinkler.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%lld",&h[i][0]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
sprinkler.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%lld",&q);
      |     ~~~~~^~~~~~~~~~~
sprinkler.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%lld",&t);
      |         ~~~~~^~~~~~~~~~~
sprinkler.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |             scanf("%lld%lld%lld",&x,&d,&w);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |             scanf("%lld",&x);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 4 ms 5460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 652 ms 95748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 652 ms 95748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 723 ms 97408 KB Output is correct
3 Correct 753 ms 97352 KB Output is correct
4 Incorrect 639 ms 97564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 704 ms 98084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 4 ms 5460 KB Output isn't correct
5 Halted 0 ms 0 KB -