Submission #1022382

#TimeUsernameProblemLanguageResultExecution timeMemory
1022382NintsiChkhaidzeSprinkler (JOI22_sprinkler)C++17
100 / 100
1114 ms104348 KiB
#include <bits/stdc++.h> #include <ostream> #define pb push_back #define s second #define f first #define pb push_back #define pii pair <int,int> #define ll long long #define left h*2,l,(l + r)/2 #define right h*2+1,(l + r)/2 + 1,r #define int ll using namespace std; const int N = 3e5 + 5; int mod,par[N],h[N],a[N][45]; vector <int> v[N]; void dfs(int x,int parent){ par[x] = parent; for (int to: v[x]){ if (to == parent) continue; dfs(to,x); } } signed main() { ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); int n; cin>>n>>mod; for (int i = 1; i < n; i++){ int a,b; cin>>a>>b; v[a].pb(b); v[b].pb(a); } for (int i = n + 45; i >= n + 1; i--){ v[i].pb(i - 1); } dfs(n + 45,0); for (int i= 1; i <= n; i++) cin >> h[i]; int q; cin>>q; for (int i = 1; i <= n + 45; i++) for (int j = 0; j <= 45; j++) a[i][j] = 1; while (q--){ int tp; cin>>tp; if (tp == 1){ int x,d,w; cin>>x>>d>>w; for (int i = 0; i <= d; i++){ a[x][d - i] = (a[x][d - i] * w) % mod; x = par[x]; } continue; } int x; cin>>x; int X = x; int ans = h[x]; for (int i = 0; i <= 40; i++){ ans = ans * a[x][i] % mod; x = par[x]; } x = X; for (int i = 0; i <= 40; i++){ ans = ans * a[x][i + 1] % mod; x = par[x]; } cout<<ans<<endl; } }

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:52:15: warning: iteration 45 invokes undefined behavior [-Waggressive-loop-optimizations]
   52 |       a[i][j] = 1;
      |       ~~~~~~~~^~~
sprinkler.cpp:51:23: note: within this loop
   51 |     for (int j = 0; j <= 45; j++)
      |                     ~~^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...