Submission #568468

#	Time	Username	Problem	Language	Result	Execution time	Memory
568468		dantoh000	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	1255 ms	102600 KiB

sprinkler

#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 && d <= 40) 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 (stderr)

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: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17