oj.uz

Submission #551920

# Submission time Handle Problem Language Result Execution time Memory
551920 2022-04-21T22:19:49 Z QwertyPi Sprinkler (JOI22_sprinkler) C++14
0 / 100
 4000 ms 94368 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
using namespace std;

const int N = 2e5 + 5, D = 41;
int n, L;
int h[N], p[N], d[N];
vector<int> G[N];
int dp[N][D];

void dfs(int x, int par = -1){
	for(auto i : G[x]){
		if(i != par){
			d[i] = d[x] + 1;
			dfs(i, x);
			p[i] = x;
		}
	}
}

int lay[D];
void upd(int x, int d, int w){
	int idx = 0;
	while(x != 0 && idx <= d){
		lay[idx++] = x;
		x = p[x];
	}
	int mx = 0;
	for(int i = idx - 1; i >= 0; i--){
		int l = mx, r = d - i;
		for(int j = l; j <= r; j++){
			dp[lay[i]][j] = (dp[lay[i]][j] * w) % L;
		}
		mx = r;
	}
}

int qry(int x){
	int ret = h[x];
	for(int i = 0; i <= D && x > 0; i++){
		ret = ret * dp[x][i] % L;
		x = p[x];
	}
	return ret;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	for(int i = 0; i < N; i++) for(int j = 0; j < D; j++) dp[i][j] = 1;
	cin >> n >> L;
	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1);
	for(int i = 1; i <= n; i++) cin >> h[i];
	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
		int t; cin >> t;
		if(t == 1){
			int x, d, w;
			cin >> x >> d >> w; 
			upd(x, d, w);
		}else{
			int x;
			cin >> x;
			cout << qry(x) << endl;
		}
	}
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 69104 KB Output is correct
2 Execution timed out 4100 ms 89712 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 69104 KB Output is correct
2 Execution timed out 4100 ms 89712 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 69096 KB Output is correct
2 Execution timed out 4027 ms 94368 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 69192 KB Output is correct
2 Execution timed out 4083 ms 90332 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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