Submission #991582

#	Time	Username	Problem	Language	Result	Execution time	Memory
991582		snpmrnhlol	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	505 ms	64596 KiB

sprinkler

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int D = 45;
vector <int> e[N];
vector <int> path;
int pr[N];
int bonus[N][D];
int v[N];
void dfs(int node, int p){
    pr[node] = p;
    for(auto i:e[node]){
        if(i == p)continue;
        dfs(i, node);
    }

}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,mod;
    cin>>n>>mod;
    for(int i = 0;i < n - 1;i++){
        int u,w;
        cin>>u>>w;
        e[u - 1].push_back(w - 1);
        e[w - 1].push_back(u - 1);
    }
    for(int i = 0;i < n;i++){
        cin>>v[i];
        for(int j = 0;j <= D;j++){
            bonus[i][j] = 1;
        }
    }
    dfs(0, -1);
    int q;
    cin>>q;
    for(int i = 0;i < q;i++){
        int tip;
        cin>>tip;
        ///limit:40
        if(tip == 1){
            int x,d,w;
            cin>>x>>d>>w;
            x--;
            int cnt = 0;
            for(int j = x;j != -1 && cnt <= d;j = pr[j]){
                bonus[j][d - cnt] = 1ll*bonus[j][d - cnt]*w%mod;
                //cout<<"update:"<<j<<' '<<d - cnt<<' '<<w<<'\n';
                cnt++;
            }
        }else{
            int x;
            cin>>x;
            x--;
            int ans = v[x];
            for(int j = 0;j < D && x != -1;j++){
                if(x == 0){
                    for(int k = j;k < D;k++){
                        ans = 1ll*ans*bonus[x][k]%mod;
                    }
                }else{
                    ans = 1ll*ans*bonus[x][j]%mod;
                    if(j != D - 1){
                        ans = 1ll*ans*bonus[x][j + 1]%mod;
                    }
                }
                x = pr[x];
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:32:25: warning: iteration 45 invokes undefined behavior [-Waggressive-loop-optimizations]
   32 |             bonus[i][j] = 1;
      |             ~~~~~~~~~~~~^~~
sprinkler.cpp:31:25: note: within this loop
   31 |         for(int j = 0;j <= D;j++){
      |                       ~~^~~~

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17