oj.uz

Submission #571906

# Submission time Handle Problem Language Result Execution time Memory
571906 2022-06-03T06:49:46 Z 8e7 Sprinkler (JOI22_sprinkler) C++17
38 / 100
 831 ms 276416 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 4
#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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 35412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17492 KB Output is correct
2 Correct 663 ms 132924 KB Output is correct
3 Correct 744 ms 141088 KB Output is correct
4 Correct 697 ms 143600 KB Output is correct
5 Correct 689 ms 140672 KB Output is correct
6 Correct 686 ms 140176 KB Output is correct
7 Correct 701 ms 143256 KB Output is correct
8 Correct 649 ms 145656 KB Output is correct
9 Correct 647 ms 148468 KB Output is correct
10 Correct 676 ms 147820 KB Output is correct
11 Correct 655 ms 139980 KB Output is correct
12 Correct 689 ms 138572 KB Output is correct
13 Correct 524 ms 145708 KB Output is correct
14 Correct 582 ms 146236 KB Output is correct
15 Correct 548 ms 141520 KB Output is correct
16 Correct 646 ms 145196 KB Output is correct
17 Correct 674 ms 143252 KB Output is correct
18 Correct 9 ms 17492 KB Output is correct
19 Correct 10 ms 17556 KB Output is correct
20 Correct 11 ms 17564 KB Output is correct
21 Correct 10 ms 17492 KB Output is correct
22 Correct 12 ms 17504 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17492 KB Output is correct
2 Correct 663 ms 132924 KB Output is correct
3 Correct 744 ms 141088 KB Output is correct
4 Correct 697 ms 143600 KB Output is correct
5 Correct 689 ms 140672 KB Output is correct
6 Correct 686 ms 140176 KB Output is correct
7 Correct 701 ms 143256 KB Output is correct
8 Correct 649 ms 145656 KB Output is correct
9 Correct 647 ms 148468 KB Output is correct
10 Correct 676 ms 147820 KB Output is correct
11 Correct 655 ms 139980 KB Output is correct
12 Correct 689 ms 138572 KB Output is correct
13 Correct 524 ms 145708 KB Output is correct
14 Correct 582 ms 146236 KB Output is correct
15 Correct 548 ms 141520 KB Output is correct
16 Correct 646 ms 145196 KB Output is correct
17 Correct 674 ms 143252 KB Output is correct
18 Correct 9 ms 17492 KB Output is correct
19 Correct 10 ms 17556 KB Output is correct
20 Correct 11 ms 17564 KB Output is correct
21 Correct 10 ms 17492 KB Output is correct
22 Correct 12 ms 17504 KB Output is correct
23 Correct 12 ms 17492 KB Output is correct
24 Correct 689 ms 140624 KB Output is correct
25 Correct 824 ms 140624 KB Output is correct
26 Correct 723 ms 148000 KB Output is correct
27 Correct 718 ms 140172 KB Output is correct
28 Correct 697 ms 142096 KB Output is correct
29 Correct 751 ms 142676 KB Output is correct
30 Correct 619 ms 146224 KB Output is correct
31 Correct 628 ms 143432 KB Output is correct
32 Correct 827 ms 146852 KB Output is correct
33 Correct 745 ms 140284 KB Output is correct
34 Correct 831 ms 140392 KB Output is correct
35 Correct 11 ms 17492 KB Output is correct
36 Correct 10 ms 17492 KB Output is correct
37 Correct 9 ms 17492 KB Output is correct
38 Correct 10 ms 17492 KB Output is correct
39 Correct 10 ms 17492 KB Output is correct
40 Correct 10 ms 17512 KB Output is correct
41 Correct 10 ms 17580 KB Output is correct
42 Correct 10 ms 17492 KB Output is correct
43 Correct 10 ms 17560 KB Output is correct
44 Correct 12 ms 17492 KB Output is correct
45 Correct 13 ms 17488 KB Output is correct
46 Correct 10 ms 17556 KB Output is correct
47 Correct 13 ms 17560 KB Output is correct
48 Correct 13 ms 17492 KB Output is correct
49 Correct 10 ms 17492 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17492 KB Output is correct
2 Runtime error 446 ms 276416 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 35412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 35412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -