oj.uz

Submission #574870

# Submission time Handle Problem Language Result Execution time Memory
574870 2022-06-09T12:41:34 Z MateGiorbelidze Sprinkler (JOI22_sprinkler) C++14
0 / 100
 737 ms 91988 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define sc second
#define pb push_back
#define in insert

ll p[201000] , h[200001] , d[201000][40];
vector<ll> g[200001];

void dfs(ll v, ll par) {
	for (auto k :g[v]){
		if (k == par) continue;
		p[k] = v;
		dfs(k , v);
	}
	
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n, mod; cin>>n>>mod;
    
    for (int i = 1; i < n; i++) {
    	ll u , v; cin>>u>>v;
    	g[u].pb(v);
    	g[v].pb(u);
	}
	
	dfs(1 , 1);
	
	p[1] = n + 1;
	for(int i = n + 2; i <= n + 40; i++){
		p[i - 1] = i;
	}
	
	for (int i = 1; i <= n; i++) {
    	cin>>h[i];
	}
	
	for (int i = 1; i <= n + 40; i++) {
    	for (int j = 0; j <= 40; j++) {
    		d[i][j] = 1;
		}
	}
	
	ll q; cin>>q;
	
	for (int o = 1; o <= q; o++) {
		
		ll tp; cin>>tp;
		
		if (tp == 2) {
			
			ll v , ans = 1; cin>>v;
			
			ans = h[v];
			
			ll j = 0;
			
			while (j <= 40) {
				
				ans *= d[v][j];
				ans %= mod;
				
				v = p[v];
				j++;
			}
			
			cout<<ans<<"\n";
			
		}
		else {
			
			ll v, r, mul; cin>>v>>r>>mul;
			
			
			ll j = r;
			
			while (j > 0) {
				
				d[v][j] *= mul;
				d[v][j] %= mod;
				
				d[v][j - 1] *= mul;
				d[v][j - 1] %= mod;
				
				v = p[v];
				j--;
			}
			d[v][j] *= mul;
			d[v][j] %= mod;
			
		}
		
	}
    
}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:48:15: warning: iteration 40 invokes undefined behavior [-Waggressive-loop-optimizations]
   48 |       d[i][j] = 1;
      |       ~~~~~~~~^~~
sprinkler.cpp:47:24: note: within this loop
   47 |      for (int j = 0; j <= 40; j++) {
      |                      ~~^~~~~
sprinkler.cpp:68:18: warning: iteration 40 invokes undefined behavior [-Waggressive-loop-optimizations]
   68 |     ans *= d[v][j];
      |            ~~~~~~^
sprinkler.cpp:66:13: note: within this loop
   66 |    while (j <= 40) {
      |           ~~^~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 5 ms 5448 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 5024 KB Output is correct
2 Incorrect 651 ms 89756 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 5024 KB Output is correct
2 Incorrect 651 ms 89756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 737 ms 91292 KB Output isn't correct
3 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 698 ms 91988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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