oj.uz

Submission #638657

# Submission time Handle Problem Language Result Execution time Memory
638657 2022-09-06T17:06:08 Z valerikk Sprinkler (JOI22_sprinkler) C++17
12 / 100
 792 ms 84208 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, ll 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;
			ll 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 4 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 5332 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 4948 KB Output is correct
2 Incorrect 517 ms 81508 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 517 ms 81508 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 2 ms 4948 KB Output is correct
2 Correct 599 ms 83020 KB Output is correct
3 Correct 669 ms 81288 KB Output is correct
4 Correct 525 ms 81784 KB Output is correct
5 Correct 511 ms 78252 KB Output is correct
6 Correct 365 ms 78540 KB Output is correct
7 Correct 398 ms 78552 KB Output is correct
8 Correct 324 ms 79056 KB Output is correct
9 Correct 699 ms 81836 KB Output is correct
10 Correct 720 ms 81844 KB Output is correct
11 Correct 554 ms 78664 KB Output is correct
12 Correct 674 ms 77888 KB Output is correct
13 Correct 458 ms 78900 KB Output is correct
14 Correct 454 ms 79324 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 3 ms 4996 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 Correct 3 ms 4948 KB Output is correct
2 Correct 646 ms 84208 KB Output is correct
3 Incorrect 792 ms 80332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5332 KB Output isn't correct
5 Halted 0 ms 0 KB -