oj.uz

Submission #588783

# Submission time Handle Problem Language Result Execution time Memory
588783 2022-07-04T04:46:27 Z SeDunion Sprinkler (JOI22_sprinkler) C++17
9 / 100
 570 ms 96628 KB 
#include<iostream>
#include<vector>

using namespace std;
using ll = long long;
const int N = 5e5 + 123;

const int LOG = 20;

const int D = 41;

ll h[N], q[N][D];

int n, L;

void mult(ll &a, ll b) {
	a *= b;
	a %= L;
}

vector<int>g[N];

int pr[N];

void dfs(int v) {
	for (int to : g[v]) if (to != pr[v]) {
		pr[to] = v;
		dfs(to);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> L;
	for (int i = 1 ; i < n ; ++ i) {
		int a, b;
		cin >> a >> b;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	dfs(1);
	for (int i = 1 ; i <= n ; ++ i) {
		cin >> h[i];
		for (int j = 0 ; j <= 40 ; ++ j) {
			q[i][j] = 1;
		}
	}
	int qq;
	cin >> qq;
	for (int i = 0 ; i < qq ; ++ i) {
		int t, x, d, w;
		cin >> t;
		if (t == 1) {
			cin >> x >> d >> w;
			for (int i = d ; i >= 0 ; -- i) {
				mult(q[x][i], w);
			}
			for (int i = 0 ; i <= d ; ++ i) {
				mult(h[x], w);
				if (x == 1) break;
				x = pr[x];
			}
		} else {
			cin >> x;
			ll ans = h[x];
			for (int i = 1 ; i <= 40 ; ++ i) {
				if (x == 1) break;
				x = pr[x];
				mult(ans, q[x][i]);
			}
			cout << ans << "\n";
		}
	}
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12088 KB Output is correct
2 Correct 6 ms 12088 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Incorrect 7 ms 12480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 525 ms 92252 KB Output is correct
3 Correct 350 ms 88944 KB Output is correct
4 Correct 445 ms 94144 KB Output is correct
5 Correct 399 ms 89852 KB Output is correct
6 Correct 319 ms 89008 KB Output is correct
7 Correct 302 ms 89192 KB Output is correct
8 Correct 262 ms 89592 KB Output is correct
9 Correct 570 ms 96628 KB Output is correct
10 Correct 363 ms 92512 KB Output is correct
11 Correct 493 ms 90184 KB Output is correct
12 Correct 344 ms 87020 KB Output is correct
13 Correct 239 ms 87580 KB Output is correct
14 Correct 234 ms 87600 KB Output is correct
15 Correct 250 ms 87660 KB Output is correct
16 Correct 237 ms 87244 KB Output is correct
17 Correct 250 ms 87816 KB Output is correct
18 Correct 7 ms 12096 KB Output is correct
19 Correct 6 ms 12116 KB Output is correct
20 Correct 6 ms 12116 KB Output is correct
21 Correct 6 ms 12116 KB Output is correct
22 Correct 6 ms 12092 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 525 ms 92252 KB Output is correct
3 Correct 350 ms 88944 KB Output is correct
4 Correct 445 ms 94144 KB Output is correct
5 Correct 399 ms 89852 KB Output is correct
6 Correct 319 ms 89008 KB Output is correct
7 Correct 302 ms 89192 KB Output is correct
8 Correct 262 ms 89592 KB Output is correct
9 Correct 570 ms 96628 KB Output is correct
10 Correct 363 ms 92512 KB Output is correct
11 Correct 493 ms 90184 KB Output is correct
12 Correct 344 ms 87020 KB Output is correct
13 Correct 239 ms 87580 KB Output is correct
14 Correct 234 ms 87600 KB Output is correct
15 Correct 250 ms 87660 KB Output is correct
16 Correct 237 ms 87244 KB Output is correct
17 Correct 250 ms 87816 KB Output is correct
18 Correct 7 ms 12096 KB Output is correct
19 Correct 6 ms 12116 KB Output is correct
20 Correct 6 ms 12116 KB Output is correct
21 Correct 6 ms 12116 KB Output is correct
22 Correct 6 ms 12092 KB Output is correct
23 Correct 6 ms 11988 KB Output is correct
24 Incorrect 498 ms 89344 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12052 KB Output is correct
2 Incorrect 558 ms 92592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Incorrect 564 ms 93188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12088 KB Output is correct
2 Correct 6 ms 12088 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Incorrect 7 ms 12480 KB Output isn't correct
5 Halted 0 ms 0 KB -