Submission #922028

#	Time	Username	Problem	Language	Result	Execution time	Memory
922028		OAleksa	Sprinkler (JOI22_sprinkler)	C++14	12 / 100	1139 ms	89056 KiB

sprinkler

#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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 12 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17