oj.uz

Submission #917479

# Submission time Handle Problem Language Result Execution time Memory
917479 2024-01-28T09:35:01 Z PotatoMan Sprinkler (JOI22_sprinkler) C++14
12 / 100
 1352 ms 89572 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;
					bit[cur][40-td+1] %= mod;
					if( td != 0 ) {
						bit[cur][40-td+2] *= tw;
						bit[cur][40-td+2] %= mod;
					}
				}
				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 344 KB Output is correct
3 Correct 0 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 348 KB Output is correct
2 Incorrect 443 ms 89572 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 348 KB Output is correct
2 Incorrect 443 ms 89572 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 344 KB Output is correct
2 Correct 743 ms 85864 KB Output is correct
3 Correct 1295 ms 85240 KB Output is correct
4 Correct 805 ms 85600 KB Output is correct
5 Correct 472 ms 86748 KB Output is correct
6 Correct 305 ms 86868 KB Output is correct
7 Correct 333 ms 87228 KB Output is correct
8 Correct 225 ms 87968 KB Output is correct
9 Correct 766 ms 85960 KB Output is correct
10 Correct 1352 ms 85228 KB Output is correct
11 Correct 495 ms 86804 KB Output is correct
12 Correct 614 ms 86368 KB Output is correct
13 Correct 323 ms 87180 KB Output is correct
14 Correct 337 ms 87952 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 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 793 ms 88768 KB Output is correct
3 Correct 1309 ms 85524 KB Output is correct
4 Correct 751 ms 87096 KB Output is correct
5 Incorrect 479 ms 87964 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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -