oj.uz

Submission #638652

# Submission time Handle Problem Language Result Execution time Memory
638652 2022-09-06T16:34:41 Z valerikk Sprinkler (JOI22_sprinkler) C++17
12 / 100
 810 ms 83368 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);
			if (d != 0) {
				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 5028 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 567 ms 81792 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 567 ms 81792 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 633 ms 83368 KB Output is correct
3 Correct 707 ms 81468 KB Output is correct
4 Correct 577 ms 81900 KB Output is correct
5 Correct 523 ms 78504 KB Output is correct
6 Correct 375 ms 78764 KB Output is correct
7 Correct 385 ms 78776 KB Output is correct
8 Correct 312 ms 79164 KB Output is correct
9 Correct 622 ms 82040 KB Output is correct
10 Correct 810 ms 82072 KB Output is correct
11 Correct 565 ms 79052 KB Output is correct
12 Correct 698 ms 78348 KB Output is correct
13 Correct 438 ms 79236 KB Output is correct
14 Correct 533 ms 79332 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5020 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5000 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 5028 KB Output isn't correct
2 Halted 0 ms 0 KB -