oj.uz

Submission #638656

# Submission time Handle Problem Language Result Execution time Memory
638656 2022-09-06T17:04:21 Z valerikk Sprinkler (JOI22_sprinkler) C++17
12 / 100
 709 ms 92188 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 50;
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, int p) {
	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];
	}
	for (int i = n; i < n + D; ++i) {
		g[i].push_back(i + 1);
		g[i + 1].push_back(i);
	}
	g[0].push_back(n);
	g[n].push_back(0);
	dfs(n + D, n + D);
	for (int i = 0; i <= n + D; ++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 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 4 ms 5372 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB Output is correct
2 Incorrect 533 ms 81656 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 5020 KB Output is correct
2 Incorrect 533 ms 81656 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 587 ms 83284 KB Output is correct
3 Correct 671 ms 81408 KB Output is correct
4 Correct 542 ms 81928 KB Output is correct
5 Correct 492 ms 78508 KB Output is correct
6 Correct 370 ms 78576 KB Output is correct
7 Correct 350 ms 78868 KB Output is correct
8 Correct 311 ms 79228 KB Output is correct
9 Correct 573 ms 82088 KB Output is correct
10 Correct 664 ms 82064 KB Output is correct
11 Correct 536 ms 78900 KB Output is correct
12 Correct 594 ms 78280 KB Output is correct
13 Correct 442 ms 79200 KB Output is correct
14 Correct 429 ms 79456 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 635 ms 92188 KB Output is correct
3 Incorrect 709 ms 89916 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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