oj.uz

Submission #922028

# Submission time Handle Problem Language Result Execution time Memory
922028 2024-02-04T19:00:05 Z OAleksa Sprinkler (JOI22_sprinkler) C++14
12 / 100
 1139 ms 89056 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 2e5 + 69;
const int D = 44;
const int K = 18;
int up[N][K], tin[N], tout[N], timer;
int sum[N][D], sz[N], dep[N];
int n, L, a[N], par[N], q, vis[N];
vector<int> g[N];
bool anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int Lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
int Distance(int a, int b) {
	return dep[a] + dep[b] - 2 * dep[Lca(a, b)];
}
void find_sz(int v, int p) {
	if (vis[v]) {
		sz[v] = 0;
		return;
	}
	sz[v] = 1;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		find_sz(u, v);
		sz[v] += sz[u];
	}
}
void dfs(int v, int p) {
	up[v][0] = p;
	tin[v] = ++timer;
	dep[v] = dep[p] + 1;
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
	}
	tout[v] = timer;
}
int find_cent(int v, int p, int x) {
	for (auto u : g[v]) {
		if (!vis[u] && u != p && sz[u] > x / 2)
			return find_cent(u, v, x);
	}
	return v;
}
void build(int v, int p) {
	find_sz(v, -1);
	int c = find_cent(v, -1, sz[v]);
	par[c] = p;
	vis[c] = 1;
	for (auto u : g[c]) {
		if (!vis[u])
			build(u, c); 
	}
}
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);
		build(1, -1);
		cin >> q;
		while (q--) {
			int t;
			cin >> t;
			if (t == 1) {
				int x, d, w;
				cin >> x >> d >> w;
				int t = x;
				while (t != -1) {
					int dis = Distance(t, x);
					for (int i = d - dis;i >= 0;i--)
						sum[t][i] = (sum[t][i] * w) % L;
					t = par[t];
				}
			}
			else {
				int x;
				cin >> x;
				int ans = a[x];
				int t = x;
				while (t != -1) {
					int dis = Distance(t, x);
					if (dis < D)
						ans = (ans * sum[t][dis]) % L;
					t = par[t];
				}
				cout << ans << '\n';
			}
		}
  }
  return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Incorrect 696 ms 77268 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 12892 KB Output is correct
2 Incorrect 696 ms 77268 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 12888 KB Output is correct
2 Correct 763 ms 89056 KB Output is correct
3 Correct 1111 ms 86352 KB Output is correct
4 Correct 790 ms 86648 KB Output is correct
5 Correct 789 ms 74540 KB Output is correct
6 Correct 606 ms 74580 KB Output is correct
7 Correct 559 ms 74752 KB Output is correct
8 Correct 307 ms 75264 KB Output is correct
9 Correct 701 ms 84748 KB Output is correct
10 Correct 1139 ms 88428 KB Output is correct
11 Correct 677 ms 74064 KB Output is correct
12 Correct 1128 ms 75344 KB Output is correct
13 Correct 866 ms 76188 KB Output is correct
14 Correct 905 ms 76688 KB Output is correct
15 Correct 2 ms 12888 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 2 ms 12892 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -