oj.uz

Submission #964666

# Submission time Handle Problem Language Result Execution time Memory
964666 2024-04-17T09:52:41 Z yellowtoad Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 80856 KB 
#include <iostream>
#include <vector>
#define f first
#define s second
#define int long long
using namespace std;
 
int n, mod, a[200050], cnt, test, p[200050];
pair<int,int> rng[200050], grp[200050];
vector<int> edge[200050], d[200050], node[200050];
bool up;
 
void dfs(int u, int v, int depth) {
	p[u] = v;
	rng[u].f = ++cnt;
	grp[u] = {depth,d[depth].size()};
	d[depth].push_back(u);
	for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs(edge[u][i],u,depth+1);
	rng[u].s = cnt;
}
 
void build(int i, int id, int x, int y) {
	if (x == y) {
		node[i][id] = a[d[i][x]];
		return;
	}
	int mid = (x+y)/2;
	build(i,id*2,x,mid);
	build(i,id*2+1,mid+1,y);
	node[i][id] = 1;
}
 
void update(int i, int id, int x, int y, int l, int r, int val) {
	if ((l <= rng[d[i][x]].f) && (rng[d[i][y]].f <= r)) {
		(node[i][id] *= val) %= mod;
		return;
	}
	if ((rng[d[i][y]].f < l) || (r < rng[d[i][x]].f)) return;
	int mid = (x+y)/2;
	(node[i][id*2] *= node[i][id]) %= mod;
	(node[i][id*2+1] *= node[i][id]) %= mod;
	node[i][id] = 1;
	update(i,id*2,x,mid,l,r,val);
	update(i,id*2+1,mid+1,y,l,r,val);
}

int query(int i, int id, int x, int y, int pos) {
	if (x == y) return node[i][id];
	int mid = (x+y)/2;
	(node[i][id*2] *= node[i][id]) %= mod;
	(node[i][id*2+1] *= node[i][id]) %= mod;
	node[i][id] = 1;
	if (pos <= mid) return query(i,id*2,x,mid,pos);
	else return query(i,id*2+1,mid+1,y,pos);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> mod;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) cin >> a[i];
	dfs(1,0,1);
	for (int i = 1; i <= n; i++) {
		if (d[i].size()) {
			node[i].resize(d[i].size()*4+10);
			build(i,1,0,d[i].size()-1);
		}
	}
	cin >> test;
	while (test--) {
		int type, u, dis, val, depth;
		cin >> type;
		if (type == 1) {
			cin >> u >> dis >> val;
			depth = grp[u].f+dis;
			up = 0;
			while (depth >= grp[u].f) {
				if (d[depth].size()) update(depth,1,0,d[depth].size()-1,rng[u].f,rng[u].s,val);
				if ((up) && (p[u])) u = p[u];
				up = 1-up;
				depth--;
			}
		} else {
			cin >> u;
			cout << query(grp[u].f,1,0,d[grp[u].f].size()-1,grp[u].s) << "\n";
		}
	}
}

Compilation message

sprinkler.cpp: In function 'void dfs(long long int, long long int, long long int)':
sprinkler.cpp:18:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs(edge[u][i],u,depth+1);
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 5 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 5 ms 21340 KB Output is correct
5 Correct 6 ms 21080 KB Output is correct
6 Correct 5 ms 21080 KB Output is correct
7 Correct 5 ms 21332 KB Output is correct
8 Correct 6 ms 21220 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 5 ms 21152 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct
13 Correct 5 ms 21176 KB Output is correct
14 Correct 5 ms 21084 KB Output is correct
15 Correct 4 ms 21084 KB Output is correct
16 Correct 5 ms 21084 KB Output is correct
17 Correct 4 ms 21084 KB Output is correct
18 Correct 5 ms 21180 KB Output is correct
19 Correct 5 ms 21084 KB Output is correct
20 Correct 5 ms 21084 KB Output is correct
21 Correct 4 ms 21084 KB Output is correct
22 Correct 5 ms 21080 KB Output is correct
23 Correct 5 ms 21156 KB Output is correct
24 Correct 6 ms 21152 KB Output is correct
25 Correct 5 ms 21080 KB Output is correct
26 Correct 6 ms 21148 KB Output is correct
27 Correct 5 ms 21084 KB Output is correct
28 Correct 5 ms 21080 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 344 ms 47824 KB Output is correct
3 Correct 592 ms 46328 KB Output is correct
4 Correct 384 ms 67720 KB Output is correct
5 Correct 439 ms 47272 KB Output is correct
6 Correct 474 ms 46276 KB Output is correct
7 Correct 456 ms 46832 KB Output is correct
8 Correct 394 ms 47040 KB Output is correct
9 Correct 372 ms 80856 KB Output is correct
10 Correct 446 ms 76392 KB Output is correct
11 Correct 348 ms 47660 KB Output is correct
12 Correct 621 ms 46420 KB Output is correct
13 Correct 251 ms 47176 KB Output is correct
14 Correct 452 ms 45844 KB Output is correct
15 Correct 486 ms 45860 KB Output is correct
16 Correct 571 ms 46380 KB Output is correct
17 Correct 603 ms 46528 KB Output is correct
18 Correct 4 ms 21084 KB Output is correct
19 Correct 5 ms 21080 KB Output is correct
20 Correct 4 ms 21084 KB Output is correct
21 Correct 4 ms 21080 KB Output is correct
22 Correct 4 ms 21084 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 344 ms 47824 KB Output is correct
3 Correct 592 ms 46328 KB Output is correct
4 Correct 384 ms 67720 KB Output is correct
5 Correct 439 ms 47272 KB Output is correct
6 Correct 474 ms 46276 KB Output is correct
7 Correct 456 ms 46832 KB Output is correct
8 Correct 394 ms 47040 KB Output is correct
9 Correct 372 ms 80856 KB Output is correct
10 Correct 446 ms 76392 KB Output is correct
11 Correct 348 ms 47660 KB Output is correct
12 Correct 621 ms 46420 KB Output is correct
13 Correct 251 ms 47176 KB Output is correct
14 Correct 452 ms 45844 KB Output is correct
15 Correct 486 ms 45860 KB Output is correct
16 Correct 571 ms 46380 KB Output is correct
17 Correct 603 ms 46528 KB Output is correct
18 Correct 4 ms 21084 KB Output is correct
19 Correct 5 ms 21080 KB Output is correct
20 Correct 4 ms 21084 KB Output is correct
21 Correct 4 ms 21080 KB Output is correct
22 Correct 4 ms 21084 KB Output is correct
23 Correct 5 ms 21084 KB Output is correct
24 Correct 375 ms 48196 KB Output is correct
25 Correct 837 ms 46656 KB Output is correct
26 Correct 397 ms 78620 KB Output is correct
27 Correct 437 ms 47296 KB Output is correct
28 Correct 561 ms 46924 KB Output is correct
29 Correct 516 ms 46600 KB Output is correct
30 Correct 321 ms 46992 KB Output is correct
31 Correct 344 ms 69712 KB Output is correct
32 Correct 507 ms 70400 KB Output is correct
33 Correct 340 ms 43464 KB Output is correct
34 Correct 903 ms 40412 KB Output is correct
35 Correct 4 ms 21084 KB Output is correct
36 Correct 4 ms 21148 KB Output is correct
37 Correct 4 ms 21084 KB Output is correct
38 Correct 4 ms 21084 KB Output is correct
39 Correct 4 ms 21084 KB Output is correct
40 Correct 4 ms 21084 KB Output is correct
41 Correct 5 ms 21084 KB Output is correct
42 Correct 4 ms 21156 KB Output is correct
43 Correct 5 ms 21084 KB Output is correct
44 Correct 4 ms 21084 KB Output is correct
45 Correct 4 ms 21084 KB Output is correct
46 Correct 4 ms 21336 KB Output is correct
47 Correct 5 ms 21140 KB Output is correct
48 Correct 4 ms 21084 KB Output is correct
49 Correct 4 ms 21084 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20912 KB Output is correct
2 Correct 662 ms 73364 KB Output is correct
3 Correct 2773 ms 63664 KB Output is correct
4 Correct 1018 ms 65904 KB Output is correct
5 Correct 2824 ms 40276 KB Output is correct
6 Correct 1672 ms 40144 KB Output is correct
7 Correct 934 ms 40228 KB Output is correct
8 Correct 222 ms 39992 KB Output is correct
9 Correct 594 ms 62836 KB Output is correct
10 Correct 2313 ms 69556 KB Output is correct
11 Correct 1281 ms 41052 KB Output is correct
12 Execution timed out 4056 ms 40256 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Correct 626 ms 63820 KB Output is correct
3 Correct 2859 ms 55624 KB Output is correct
4 Correct 1110 ms 60592 KB Output is correct
5 Correct 2785 ms 41976 KB Output is correct
6 Correct 1640 ms 41492 KB Output is correct
7 Correct 907 ms 41112 KB Output is correct
8 Correct 260 ms 41396 KB Output is correct
9 Correct 676 ms 73808 KB Output is correct
10 Correct 2268 ms 71176 KB Output is correct
11 Correct 1357 ms 43176 KB Output is correct
12 Execution timed out 4054 ms 40276 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21084 KB Output is correct
2 Correct 5 ms 21080 KB Output is correct
3 Correct 4 ms 21084 KB Output is correct
4 Correct 5 ms 21340 KB Output is correct
5 Correct 6 ms 21080 KB Output is correct
6 Correct 5 ms 21080 KB Output is correct
7 Correct 5 ms 21332 KB Output is correct
8 Correct 6 ms 21220 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 5 ms 21152 KB Output is correct
11 Correct 4 ms 21084 KB Output is correct
12 Correct 4 ms 21084 KB Output is correct
13 Correct 5 ms 21176 KB Output is correct
14 Correct 5 ms 21084 KB Output is correct
15 Correct 4 ms 21084 KB Output is correct
16 Correct 5 ms 21084 KB Output is correct
17 Correct 4 ms 21084 KB Output is correct
18 Correct 5 ms 21180 KB Output is correct
19 Correct 5 ms 21084 KB Output is correct
20 Correct 5 ms 21084 KB Output is correct
21 Correct 4 ms 21084 KB Output is correct
22 Correct 5 ms 21080 KB Output is correct
23 Correct 5 ms 21156 KB Output is correct
24 Correct 6 ms 21152 KB Output is correct
25 Correct 5 ms 21080 KB Output is correct
26 Correct 6 ms 21148 KB Output is correct
27 Correct 5 ms 21084 KB Output is correct
28 Correct 5 ms 21080 KB Output is correct
29 Correct 5 ms 21084 KB Output is correct
30 Correct 344 ms 47824 KB Output is correct
31 Correct 592 ms 46328 KB Output is correct
32 Correct 384 ms 67720 KB Output is correct
33 Correct 439 ms 47272 KB Output is correct
34 Correct 474 ms 46276 KB Output is correct
35 Correct 456 ms 46832 KB Output is correct
36 Correct 394 ms 47040 KB Output is correct
37 Correct 372 ms 80856 KB Output is correct
38 Correct 446 ms 76392 KB Output is correct
39 Correct 348 ms 47660 KB Output is correct
40 Correct 621 ms 46420 KB Output is correct
41 Correct 251 ms 47176 KB Output is correct
42 Correct 452 ms 45844 KB Output is correct
43 Correct 486 ms 45860 KB Output is correct
44 Correct 571 ms 46380 KB Output is correct
45 Correct 603 ms 46528 KB Output is correct
46 Correct 4 ms 21084 KB Output is correct
47 Correct 5 ms 21080 KB Output is correct
48 Correct 4 ms 21084 KB Output is correct
49 Correct 4 ms 21080 KB Output is correct
50 Correct 4 ms 21084 KB Output is correct
51 Correct 5 ms 21084 KB Output is correct
52 Correct 375 ms 48196 KB Output is correct
53 Correct 837 ms 46656 KB Output is correct
54 Correct 397 ms 78620 KB Output is correct
55 Correct 437 ms 47296 KB Output is correct
56 Correct 561 ms 46924 KB Output is correct
57 Correct 516 ms 46600 KB Output is correct
58 Correct 321 ms 46992 KB Output is correct
59 Correct 344 ms 69712 KB Output is correct
60 Correct 507 ms 70400 KB Output is correct
61 Correct 340 ms 43464 KB Output is correct
62 Correct 903 ms 40412 KB Output is correct
63 Correct 4 ms 21084 KB Output is correct
64 Correct 4 ms 21148 KB Output is correct
65 Correct 4 ms 21084 KB Output is correct
66 Correct 4 ms 21084 KB Output is correct
67 Correct 4 ms 21084 KB Output is correct
68 Correct 4 ms 21084 KB Output is correct
69 Correct 5 ms 21084 KB Output is correct
70 Correct 4 ms 21156 KB Output is correct
71 Correct 5 ms 21084 KB Output is correct
72 Correct 4 ms 21084 KB Output is correct
73 Correct 4 ms 21084 KB Output is correct
74 Correct 4 ms 21336 KB Output is correct
75 Correct 5 ms 21140 KB Output is correct
76 Correct 4 ms 21084 KB Output is correct
77 Correct 4 ms 21084 KB Output is correct
78 Correct 5 ms 20912 KB Output is correct
79 Correct 662 ms 73364 KB Output is correct
80 Correct 2773 ms 63664 KB Output is correct
81 Correct 1018 ms 65904 KB Output is correct
82 Correct 2824 ms 40276 KB Output is correct
83 Correct 1672 ms 40144 KB Output is correct
84 Correct 934 ms 40228 KB Output is correct
85 Correct 222 ms 39992 KB Output is correct
86 Correct 594 ms 62836 KB Output is correct
87 Correct 2313 ms 69556 KB Output is correct
88 Correct 1281 ms 41052 KB Output is correct
89 Execution timed out 4056 ms 40256 KB Time limit exceeded
90 Halted 0 ms 0 KB -