oj.uz

Submission #638651

# Submission time Handle Problem Language Result Execution time Memory
638651 2022-09-06T16:33:49 Z valerikk Sprinkler (JOI22_sprinkler) C++17
12 / 100
 716 ms 91120 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;
const int D = 41;

int n;
ll L;
vector<int> g[N];
ll h[N];
int par[N];
ll a[N][D];

void dfs(int u = 0, int p = 0) {
	par[u] = p;
	for (int v : g[u]) {
		if (v != p) {
			dfs(v, u);
		}
	}
}

void upd(int v, int d, int w) {
	for (int i = 0; i <= d; ++i, v = par[v]) {
		(a[v][d - i] *= w) %= L;
	}
}

int get(int v) {
	int res = 1;
	for (int i = 0; i < D; ++i, v = par[v]) {
		(res *= a[v][i]) %= L;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> L;
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}
	dfs(0, 0);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < D; ++j) {
			a[i][j] = 1;
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			--x;
			upd(x, d, w);
			upd(x, d - 1, w);
		}
		if (t == 2) {
			int x;
			cin >> x;
			--x;
			cout << h[x] * get(x) % L << "\n";
		}
	}
	return 0;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 516 ms 89588 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 3 ms 4948 KB Output is correct
2 Correct 615 ms 91068 KB Output is correct
3 Correct 716 ms 90640 KB Output is correct
4 Correct 538 ms 90184 KB Output is correct
5 Correct 528 ms 86920 KB Output is correct
6 Correct 393 ms 87292 KB Output is correct
7 Correct 396 ms 87116 KB Output is correct
8 Correct 330 ms 87736 KB Output is correct
9 Correct 570 ms 89748 KB Output is correct
10 Correct 680 ms 91120 KB Output is correct
11 Correct 528 ms 86664 KB Output is correct
12 Correct 651 ms 87432 KB Output is correct
13 Correct 454 ms 88404 KB Output is correct
14 Correct 536 ms 88836 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 5028 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 3 ms 5024 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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