oj.uz

Submission #784293

# Submission time Handle Problem Language Result Execution time Memory
784293 2023-07-16T01:17:12 Z TakeMe Sprinkler (JOI22_sprinkler) C++14
9 / 100
 694 ms 101992 KB 
/* Quick Note :
 * Jangan Mikir Lama - lama, sampahin dulu aja kalo OI
 * Always Try to reset
*/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
const ld PI = 4*atan((ld)1);
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll nax = 2e5 + 5;

ll n, q, len;
ll a[nax], par[nax], val[nax];
ll child_mul[nax][45];
vector<ll> v[nax];

void find_par(ll x, ll y){
	par[x] = y;
	for(auto it : v[x]){
		if(it == y) continue;
		else{
			find_par(it, x);
		}
	}
}

void dfs_update(ll x, ll dis, ll w){
	if(dis < 0 || x == 0) return;
	val[x] *= w;
	val[x] %= len;
	dfs_update(par[x], dis - 1, w);
}

ll dfs_query(ll x, ll dis){
	if(dis >= 41 || x == 0) return 1;
	ll ret = child_mul[x][dis];
	//cout << child_mul[x][dis] << " " << x << " " << dis << '\n';
	return (ret * dfs_query(par[x], dis + 1)) % len;
}

int main(){ 
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    
    cin >> n >> len;
    for(ll i = 1; i <= n ; i++){
		for(ll j = 1; j <= 40; j++){
			child_mul[i][j] = 1;
		}
	}
    for(ll i = 1; i < n; i++){
		ll x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	for(ll i = 1; i <= n; i++){
		cin >> val[i];
	}
	find_par(1, 0);
	cin >> q;
	while(q--){
		ll tp;
		cin >> tp;
		if(tp == 1){
			ll x, d, w;
			cin >> x >> d >> w;
			for(ll i = 1; i <= d; i++){
				child_mul[x][i] *= w;
				child_mul[x][i] %= len;
			}
			val[x] *= w;
			val[x] %= len;
			dfs_update(par[x], d - 1, w);
		}
		else{
			ll x;
			cin >> x;
			ll ans = val[x] * dfs_query(par[x], 1);
			
			cout << ans % len << '\n';
		}
	}
}

Subtask #1
0 / 3.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 527 ms 97684 KB Output is correct
3 Correct 301 ms 98172 KB Output is correct
4 Correct 468 ms 100268 KB Output is correct
5 Correct 402 ms 97984 KB Output is correct
6 Correct 273 ms 97620 KB Output is correct
7 Correct 257 ms 98332 KB Output is correct
8 Correct 200 ms 98580 KB Output is correct
9 Correct 654 ms 101860 KB Output is correct
10 Correct 315 ms 101992 KB Output is correct
11 Correct 525 ms 97580 KB Output is correct
12 Correct 280 ms 98124 KB Output is correct
13 Correct 198 ms 98200 KB Output is correct
14 Correct 210 ms 98684 KB Output is correct
15 Correct 197 ms 97924 KB Output is correct
16 Correct 198 ms 98528 KB Output is correct
17 Correct 217 ms 99184 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 5092 KB Output is correct
20 Correct 3 ms 5036 KB Output is correct
21 Correct 3 ms 5036 KB Output is correct
22 Correct 2 ms 5076 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 527 ms 97684 KB Output is correct
3 Correct 301 ms 98172 KB Output is correct
4 Correct 468 ms 100268 KB Output is correct
5 Correct 402 ms 97984 KB Output is correct
6 Correct 273 ms 97620 KB Output is correct
7 Correct 257 ms 98332 KB Output is correct
8 Correct 200 ms 98580 KB Output is correct
9 Correct 654 ms 101860 KB Output is correct
10 Correct 315 ms 101992 KB Output is correct
11 Correct 525 ms 97580 KB Output is correct
12 Correct 280 ms 98124 KB Output is correct
13 Correct 198 ms 98200 KB Output is correct
14 Correct 210 ms 98684 KB Output is correct
15 Correct 197 ms 97924 KB Output is correct
16 Correct 198 ms 98528 KB Output is correct
17 Correct 217 ms 99184 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 5092 KB Output is correct
20 Correct 3 ms 5036 KB Output is correct
21 Correct 3 ms 5036 KB Output is correct
22 Correct 2 ms 5076 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Incorrect 529 ms 97748 KB Output isn't correct
25 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 Incorrect 694 ms 98956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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