oj.uz

Submission #571905

# Submission time Handle Problem Language Result Execution time Memory
571905 2022-06-03T06:49:07 Z 8e7 Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 1039744 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define maxd 42
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int mod;
struct BIT{
	vector<vector<ll> > bit;
	int n;
	void init(int _n) {
		n = _n;
		bit.resize(maxd);
		for (int i = 0;i < maxd;i++) {
			bit[i].resize(n+1);
			for (int j = 1;j <= n;j++) bit[i][j] = 1;
		}
	}
	void modify(int ind, int d, int val) {
		//debug("mod", ind, d, val);
		ind++, d = maxd - 1 - d;
		for (;d < maxd;d += d & (-d)) {
			int tmp = ind;
			for (;ind <= n;ind += ind & (-ind)) bit[d][ind] = bit[d][ind] * val % mod;
			ind = tmp;
		}
	}	
	ll query(int ind, int d) {
		ind++, d = maxd - 1 - d;
		ll ret = 1;
		for (;d > 0;d -= d & (-d)) {
			int tmp = ind;
			for (;ind > 0;ind -= ind & (-ind)) ret = ret * bit[d][ind] % mod;
			ind = tmp;
		}
		return ret;
	}
} pref[maxn], suf[maxn];
vector<int> adj[maxn];
int par[maxn], pi[maxn], leaf[maxn];
void dfs(int n, int pa) {
	par[n] = pa;
	leaf[n] = 1;
	for (int v:adj[n]) {
		if (v != pa) {
			dfs(v, n);
			pi[v] = leaf[n]++;
		}
	}
	//debug(n, leaf[n]);
	pref[n].init(leaf[n]);
	suf[n].init(leaf[n]);
}
ll h[maxn];
void modify(int n, int d, int w) {
	int prv = 0;
	while (d >= 0 && n) {
		pref[n].modify(prv, d, w); 
		suf[n].modify(leaf[n] - 1 - prv, d, w); 
		prv = pi[n];
		n = par[n];
		d--;
	}
}
ll query(int n) {
	int cur = 0, prv = -1;
	ll ret = h[n];
	while (cur < maxd && n) {
		ret = (ret * pref[n].query(prv-1, cur) % mod * suf[n].query(leaf[n] - prv - 2, cur)%mod);
		prv = pi[n];
		n = par[n];
		cur++;
	}
	return ret;	
}
int main() {
	io
	int n;
	cin >> n >> mod;
	for (int i = 0;i < n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1;i <= n;i++) cin >> h[i]; 
	dfs(1, 0);
	int q;
	cin >> q;
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int x, d, w;
			cin >> x >> d >> w;
			modify(x, d, w);
		} else {
			int x;
			cin >> x;
			cout << query(x) << "\n";
		}
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17492 KB Output is correct
2 Correct 10 ms 17600 KB Output is correct
3 Correct 9 ms 17492 KB Output is correct
4 Correct 17 ms 22216 KB Output is correct
5 Correct 19 ms 22612 KB Output is correct
6 Correct 17 ms 22636 KB Output is correct
7 Correct 17 ms 22768 KB Output is correct
8 Correct 18 ms 22944 KB Output is correct
9 Correct 10 ms 17492 KB Output is correct
10 Correct 10 ms 17492 KB Output is correct
11 Correct 10 ms 17620 KB Output is correct
12 Correct 10 ms 17636 KB Output is correct
13 Correct 10 ms 17620 KB Output is correct
14 Correct 12 ms 17552 KB Output is correct
15 Correct 10 ms 17580 KB Output is correct
16 Correct 10 ms 17564 KB Output is correct
17 Correct 9 ms 17620 KB Output is correct
18 Correct 10 ms 17620 KB Output is correct
19 Correct 9 ms 17492 KB Output is correct
20 Correct 9 ms 17492 KB Output is correct
21 Correct 10 ms 17492 KB Output is correct
22 Correct 11 ms 17620 KB Output is correct
23 Correct 12 ms 17616 KB Output is correct
24 Correct 10 ms 17492 KB Output is correct
25 Correct 10 ms 17492 KB Output is correct
26 Correct 10 ms 17640 KB Output is correct
27 Correct 12 ms 17624 KB Output is correct
28 Correct 10 ms 17620 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17492 KB Output is correct
2 Execution timed out 4125 ms 1039744 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17492 KB Output is correct
2 Execution timed out 4125 ms 1039744 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Execution timed out 4098 ms 976976 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17492 KB Output is correct
2 Execution timed out 4108 ms 973856 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17492 KB Output is correct
2 Correct 10 ms 17600 KB Output is correct
3 Correct 9 ms 17492 KB Output is correct
4 Correct 17 ms 22216 KB Output is correct
5 Correct 19 ms 22612 KB Output is correct
6 Correct 17 ms 22636 KB Output is correct
7 Correct 17 ms 22768 KB Output is correct
8 Correct 18 ms 22944 KB Output is correct
9 Correct 10 ms 17492 KB Output is correct
10 Correct 10 ms 17492 KB Output is correct
11 Correct 10 ms 17620 KB Output is correct
12 Correct 10 ms 17636 KB Output is correct
13 Correct 10 ms 17620 KB Output is correct
14 Correct 12 ms 17552 KB Output is correct
15 Correct 10 ms 17580 KB Output is correct
16 Correct 10 ms 17564 KB Output is correct
17 Correct 9 ms 17620 KB Output is correct
18 Correct 10 ms 17620 KB Output is correct
19 Correct 9 ms 17492 KB Output is correct
20 Correct 9 ms 17492 KB Output is correct
21 Correct 10 ms 17492 KB Output is correct
22 Correct 11 ms 17620 KB Output is correct
23 Correct 12 ms 17616 KB Output is correct
24 Correct 10 ms 17492 KB Output is correct
25 Correct 10 ms 17492 KB Output is correct
26 Correct 10 ms 17640 KB Output is correct
27 Correct 12 ms 17624 KB Output is correct
28 Correct 10 ms 17620 KB Output is correct
29 Correct 10 ms 17492 KB Output is correct
30 Execution timed out 4125 ms 1039744 KB Time limit exceeded
31 Halted 0 ms 0 KB -