oj.uz

Submission #922034

# Submission time Handle Problem Language Result Execution time Memory
922034 2024-02-04T20:31:28 Z OAleksa Sprinkler (JOI22_sprinkler) C++14
12 / 100
 792 ms 57472 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 2e5 + 69;
const int D = 41;
int sum[N][D], sz[N], dep[N];
int n, L, a[N], par[N], q, vis[N];
vector<int> g[N];
void dfs(int v, int p) {
	dep[v] = dep[p] + 1;
	par[v] = p;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> L;
		for (int i = 1;i <= n - 1;i++) {
			int a, b;
			cin >> a >> b;
			a += 40;
			b += 40;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		for (int i = 41;i <= 40 + n;i++)
			cin >> a[i];
		for (int i = 1;i <= 40 + n;i++) {
			for (int j = 0;j < D;j++)
				sum[i][j] = 1;
		}
		for (int i = 1;i <= 40;i++) {
			g[i].push_back(i + 1);
			g[i + 1].push_back(i);
		}
		dfs(1, 0);
		cin >> q;
		while (q--) {
			int t;
			cin >> t;
			if (t == 1) {
				int x, d, w;
				cin >> x >> d >> w;
				x += 40;
				int t = x, j = 0;
				while (t != 0 && j <= d) {
					sum[t][d - j] = (sum[t][d - j] * w) % L;
					if (j != d)
						sum[t][d - j - 1] = (sum[t][d - j - 1] * w) % L;
					j++;
					t = par[t];
				}
			}
			else {
				int x;
				cin >> x;
				x += 40;
				int ans = a[x];
				int t = x, j = 0;
				while (t != 0 && j < D) {
					ans = (ans * sum[t][j]) % L;
					j++;
					t = par[t];
				}
				cout << ans << '\n';
			}
		}
  }
  return 0;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 406 ms 50924 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 406 ms 50924 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 10840 KB Output is correct
2 Correct 686 ms 57472 KB Output is correct
3 Correct 792 ms 54468 KB Output is correct
4 Correct 532 ms 55300 KB Output is correct
5 Correct 372 ms 47764 KB Output is correct
6 Correct 307 ms 48224 KB Output is correct
7 Correct 288 ms 48044 KB Output is correct
8 Correct 259 ms 48580 KB Output is correct
9 Correct 589 ms 54540 KB Output is correct
10 Correct 766 ms 55660 KB Output is correct
11 Correct 358 ms 48284 KB Output is correct
12 Correct 399 ms 47440 KB Output is correct
13 Correct 371 ms 48468 KB Output is correct
14 Correct 319 ms 48784 KB Output is correct
15 Correct 3 ms 10840 KB Output is correct
16 Correct 3 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Incorrect 603 ms 57024 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 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Incorrect 3 ms 10844 KB Output isn't correct
5 Halted 0 ms 0 KB -