oj.uz

Submission #921193

# Submission time Handle Problem Language Result Execution time Memory
921193 2024-02-03T13:13:36 Z OAleksa Sprinkler (JOI22_sprinkler) C++14
0 / 100
 336 ms 54200 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];
int n, L, a[N], par[N], q;
vector<int> g[N];
void dfs(int v, int p) {
	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;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		for (int i = 1;i <= n;i++)
			cin >> a[i];
		for (int i = 1;i <= n;i++) {
			for (int j = 0;j < D;j++)
				sum[i][j] = 1;
		}
		dfs(1, 0);
		cin >> q;
		while (q--) {
			int t;
			cin >> t;
			if (t == 1) {
				int x, d, w;
				cin >> x >> d >> w;
				int t = x, j = 0;
				while (t != 0 && j <= d) {
					a[t] = (a[t] * w) % L;
					j++;
					t = par[t];
				}
				sum[x][d] = (sum[x][d] * w) % L;
				for (int i = D - 2;i >= 0;i--)
					sum[x][i] = (sum[x][i] * sum[x][i + 1]) % L;
			}
			else {
				int x;
				cin >> x;
				int ans = a[x];
				int t = par[x], j = 1;
				while (t != 0 && j < D) {
					ans = (ans * sum[t][j]) % L;
					t = par[x];
					j++;
				}
				cout << ans << '\n';
			}
		}
  }
  return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Incorrect 3 ms 8796 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 6768 KB Output is correct
2 Incorrect 331 ms 50984 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 6768 KB Output is correct
2 Incorrect 331 ms 50984 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Incorrect 335 ms 52876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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