oj.uz

Submission #922031

# Submission time Handle Problem Language Result Execution time Memory
922031 2024-02-04T20:02:50 Z OAleksa Sprinkler (JOI22_sprinkler) C++14
12 / 100
 780 ms 67220 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 2e5 + 69;
const int D = 44;
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 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 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 373 ms 53288 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 373 ms 53288 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 11096 KB Output is correct
2 Correct 608 ms 59476 KB Output is correct
3 Correct 780 ms 56752 KB Output is correct
4 Correct 560 ms 57324 KB Output is correct
5 Correct 408 ms 50272 KB Output is correct
6 Correct 324 ms 50252 KB Output is correct
7 Correct 275 ms 50524 KB Output is correct
8 Correct 250 ms 50884 KB Output is correct
9 Correct 630 ms 56952 KB Output is correct
10 Correct 709 ms 58064 KB Output is correct
11 Correct 381 ms 50512 KB Output is correct
12 Correct 400 ms 49744 KB Output is correct
13 Correct 316 ms 50768 KB Output is correct
14 Correct 321 ms 51492 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10840 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 10840 KB Output is correct
2 Incorrect 647 ms 67220 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 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Incorrect 3 ms 10844 KB Output isn't correct
5 Halted 0 ms 0 KB -