oj.uz

Submission #917477

# Submission time Handle Problem Language Result Execution time Memory
917477 2024-01-28T09:30:43 Z PotatoMan Sprinkler (JOI22_sprinkler) C++14
12 / 100
 805 ms 98132 KB 
#include <bits/stdc++.h>
#define inf INT_MAX
#define longlonginf LONG_LONG_MAX
#define mod 998244353
#define MAXN 200005
#define pii pair<ll,ll>
#define ll long long
#define deb(x) cerr<<"[ "<<#x<<" = "<<x<<" ]";
#define yes() cout<<"YES\n";
#define no() cout<<"NO\n";
using namespace std;
 
ll n,k,m,q,cur,z;
ll ans = 0;
string subtask;
string s;
ll bit[MAXN][45];

void update(ll x,ll y,ll d){
	for(int i = y ; i <= 41 ; i += i&(-i)){
		bit[x][i] *= d;
		bit[x][i] %= m;
	}
}

ll get_res(ll x,ll y){
	ll res = 1;
	for(int i = y ; i > 0 ; i -= i&(-i)){
		res *= bit[x][i];
		res %= m;
	}
	return res;
}

void solve(){
	cin>>n>>m;
	vector<vector<ll>> adj(n+5);
	for(int i = 0 ; i < n-1 ; i++){
		ll l,r;
		cin>>l>>r;
		adj[l].push_back(r);
		adj[r].push_back(l);
	}
	ll h[n+5];
	for(int i = 1 ; i <= n ; i++) cin>>h[i];
	ll par[n+5];
	par[1] = 0;
	queue<int> p;
	p.push(1);
	bool vis[n+5];
	memset(vis,0,sizeof(vis));
	vis[1] = 1;
	while(!p.empty()){
		ll x = p.front();
		p.pop();
		for(auto u : adj[x]){
			if(vis[u]) continue;
			par[u] = x;
			vis[u] = 1;
			p.push(u);
		}
	}
	//init
	for(int i = 1 ; i <= n ; i++){
		for(int j = 0 ; j <= 42 ; j++){
			bit[i][j] = 1;
		}
	}
	//queries
	cin>>q;
	while(q--){
		ll x;
		cin>>x;
		if( x == 1 ){
			ll tx,td,tw;
			cin>>tx>>td>>tw;
			cur = tx;
			while(td+1 && cur){
				if( cur == 1 ) update(cur,40-td+1,tw);
				else {
					bit[cur][40-td+1] *= tw;
					if( td != 0 ) bit[cur][40-td+2] *= tw;
				}
				td--;
				cur = par[cur];
			}
		}
		else{
			ll tx,td;
			cin>>tx;
			td = 0;
			cur = tx;
			ll res = h[tx];
			while(cur && td <= 40){
				if( cur == 1 ) res *= get_res(cur,40-td+1);
				else res *= bit[cur][40-td+1];
				res %= m;
				td++;
				cur = par[cur];
			}
			cout<<res<<"\n";
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//cin>>T;
	for(int i = 0 ; i < T ; i++){
		//cout<<"Case #"<<i+1<<": ";
		solve();
	}
	return 0;
}
 
/*
	out of bound for loop
	(constraint change in loop)
	forget to change bool to int
	misread -> missed subtask
	you thought u declared it huh?
	not i but x
	logical operator
	wrong example/proof
	thoroughly
	wrong variables
	thinking it wrong
	bruh just try some test case
	capitals ;-;
	wrong data structure lol
	count memory usement
	corner case
	oversized array
	orders
	statements
	size initializer
	while con
	map -> array
	wrong digits??
	swapped variables??
	check if theres any variabled
	that got declared twice
	find some pattern
	name collision
	constraints??!
	mod !!
	resets
*/

Subtask #1
0 / 3.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 497 ms 98132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 497 ms 98132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 743 ms 94056 KB Output is correct
3 Correct 733 ms 94544 KB Output is correct
4 Correct 590 ms 94024 KB Output is correct
5 Correct 490 ms 95408 KB Output is correct
6 Correct 293 ms 95568 KB Output is correct
7 Correct 278 ms 95824 KB Output is correct
8 Correct 227 ms 96704 KB Output is correct
9 Correct 702 ms 94028 KB Output is correct
10 Correct 751 ms 94544 KB Output is correct
11 Correct 461 ms 94800 KB Output is correct
12 Correct 465 ms 95572 KB Output is correct
13 Correct 337 ms 96636 KB Output is correct
14 Correct 330 ms 97552 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 732 ms 88528 KB Output is correct
3 Correct 805 ms 95032 KB Output is correct
4 Correct 637 ms 95484 KB Output is correct
5 Incorrect 433 ms 96780 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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