oj.uz

Submission #892477

# Submission time Handle Problem Language Result Execution time Memory
892477 2023-12-25T11:48:50 Z Minbaev Sprinkler (JOI22_sprinkler) C++17
21 / 100
 2842 ms 116876 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int mod= 1e9 +7;
const int N=1e5*4;

int binpow (int a, int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n-1) * a;
	else {
		int b = binpow (a, n/2);
		return b * b;
	}
}
int n,m,k,l;
vector<int>v[N],pr(N);
int dp[N][50];

void dfs(int x,int prad){
	pr[x] = prad;
	for(auto to:v[x]){
		if(prad==to)continue;
		dfs(to,x);
	}
	return;
}

int md(int a,int b)	{
	return (a*b)%l;
}
	


void solve(){
	
	cin>>n>>l;
	
	for(int i = 0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<41;j++){
			dp[i][j] = 1;
		}
	}
	
	for(int i = 1;i<=n;i++){
		int a;
		cin>>a;
		dp[i][0] = a;
	}
	
	dfs(1,-1);
	int q;
	cin>>q;
	//~ cout<<pr[2]<<endl;
	while(q--){
		int a,x,dist,cst;
		cin>>a>>x;
		if(a==1){
			cin>>dist>>cst;
			while(true){
				for(int i = dist;i>=0;i--){
					dp[x][i] = md(dp[x][i],cst);
				}
				dist--;
				if(dist<0)break;
				if(x==1)break;
				x = pr[x];
			}
		
		}
		else{
			int ans = 1;
			for(int d = 0;d<=40&&x>0;d++,x = pr[x])
				ans = md(ans,dp[x][d]);
			cout<<ans<<"\n";
		}
		
		
	}
	
}

 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt;
	while(tt--)solve();

}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 13404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13408 KB Output is correct
2 Correct 380 ms 112656 KB Output is correct
3 Correct 256 ms 113236 KB Output is correct
4 Correct 353 ms 115116 KB Output is correct
5 Correct 311 ms 112904 KB Output is correct
6 Correct 230 ms 112452 KB Output is correct
7 Correct 237 ms 113324 KB Output is correct
8 Correct 187 ms 113348 KB Output is correct
9 Correct 439 ms 116816 KB Output is correct
10 Correct 267 ms 116876 KB Output is correct
11 Correct 395 ms 112720 KB Output is correct
12 Correct 255 ms 113148 KB Output is correct
13 Correct 170 ms 113204 KB Output is correct
14 Correct 176 ms 114036 KB Output is correct
15 Correct 172 ms 112992 KB Output is correct
16 Correct 176 ms 113520 KB Output is correct
17 Correct 191 ms 114008 KB Output is correct
18 Correct 4 ms 13412 KB Output is correct
19 Correct 3 ms 13404 KB Output is correct
20 Correct 3 ms 13408 KB Output is correct
21 Correct 4 ms 13404 KB Output is correct
22 Correct 4 ms 13404 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13408 KB Output is correct
2 Correct 380 ms 112656 KB Output is correct
3 Correct 256 ms 113236 KB Output is correct
4 Correct 353 ms 115116 KB Output is correct
5 Correct 311 ms 112904 KB Output is correct
6 Correct 230 ms 112452 KB Output is correct
7 Correct 237 ms 113324 KB Output is correct
8 Correct 187 ms 113348 KB Output is correct
9 Correct 439 ms 116816 KB Output is correct
10 Correct 267 ms 116876 KB Output is correct
11 Correct 395 ms 112720 KB Output is correct
12 Correct 255 ms 113148 KB Output is correct
13 Correct 170 ms 113204 KB Output is correct
14 Correct 176 ms 114036 KB Output is correct
15 Correct 172 ms 112992 KB Output is correct
16 Correct 176 ms 113520 KB Output is correct
17 Correct 191 ms 114008 KB Output is correct
18 Correct 4 ms 13412 KB Output is correct
19 Correct 3 ms 13404 KB Output is correct
20 Correct 3 ms 13408 KB Output is correct
21 Correct 4 ms 13404 KB Output is correct
22 Correct 4 ms 13404 KB Output is correct
23 Correct 4 ms 13404 KB Output is correct
24 Incorrect 376 ms 112596 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13656 KB Output is correct
2 Correct 684 ms 113920 KB Output is correct
3 Correct 2842 ms 113596 KB Output is correct
4 Correct 815 ms 113064 KB Output is correct
5 Correct 654 ms 109904 KB Output is correct
6 Correct 488 ms 109900 KB Output is correct
7 Correct 440 ms 110528 KB Output is correct
8 Correct 233 ms 110532 KB Output is correct
9 Correct 712 ms 112324 KB Output is correct
10 Correct 2728 ms 114128 KB Output is correct
11 Correct 562 ms 109428 KB Output is correct
12 Correct 1961 ms 110416 KB Output is correct
13 Correct 1554 ms 111444 KB Output is correct
14 Correct 1570 ms 112492 KB Output is correct
15 Correct 4 ms 13400 KB Output is correct
16 Correct 3 ms 13404 KB Output is correct
17 Correct 3 ms 13404 KB Output is correct
18 Correct 4 ms 13400 KB Output is correct
19 Correct 4 ms 13400 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 13400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 13404 KB Output isn't correct
2 Halted 0 ms 0 KB -