oj.uz

Submission #544599

# Submission time Handle Problem Language Result Execution time Memory
544599 2022-04-02T13:25:09 Z sidon Sprinkler (JOI22_sprinkler) C++17
12 / 100
 654 ms 52444 KB 
#include <bits/stdc++.h>
using namespace std;

const int Z = 2e5+1, B = 42;

int N, L, H[Z][B], W, res;

#define mul(VL) if((VL *= W) >= L) VL %= L

int p[Z];
vector<int> g[Z];

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> L;

	for(int i = 1; i < N; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(1);

	for(int i = 0; i <= N; ++i)
		fill(H[i], H[i] + B, 1);

	for(int i = 1; i <= N; ++i)
		cin >> H[i][0];

	int Q, T, u, d; cin >> Q;
	for(int i = 1; i <= Q; ++i) {
		cin >> T >> u;
		if(T & 1) {
			cin >> d >> W;

			while(u) {
				mul(H[u][d]);
				if(d) {
					mul(H[u][d-1]);
					--d;
					u = p[u];
				} else break;
			}
			if(!u) {
				while(d) {
					mul(H[0][d]);
					--d;
				}
			}
		} else {
			res = H[u][0];
			u = p[u];

			for(d = 1; d < B; ++d) {
				(res *= H[u][d]) %= L;
				if(!u) break;
				u = p[u];
			}
			cout << res << '\n';
		}
	}
}

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 4 ms 4948 KB Output is correct
4 Incorrect 3 ms 5204 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 498 ms 48640 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 498 ms 48640 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 570 ms 51912 KB Output is correct
3 Correct 608 ms 49568 KB Output is correct
4 Correct 494 ms 50092 KB Output is correct
5 Correct 460 ms 45516 KB Output is correct
6 Correct 338 ms 45540 KB Output is correct
7 Correct 282 ms 45672 KB Output is correct
8 Correct 243 ms 46184 KB Output is correct
9 Correct 550 ms 50012 KB Output is correct
10 Correct 654 ms 50588 KB Output is correct
11 Correct 505 ms 45740 KB Output is correct
12 Correct 522 ms 45144 KB Output is correct
13 Correct 363 ms 46024 KB Output is correct
14 Correct 386 ms 46472 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 4928 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 Incorrect 562 ms 52444 KB Output isn't correct
3 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 4 ms 4948 KB Output is correct
4 Incorrect 3 ms 5204 KB Output isn't correct
5 Halted 0 ms 0 KB -