oj.uz

Submission #589292

# Submission time Handle Problem Language Result Execution time Memory
589292 2022-07-04T11:58:47 Z Tekor Sprinkler (JOI22_sprinkler) C++17
100 / 100
 723 ms 88656 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define f first
#define s second
#define pii pair <int,int>
#define en '\n'
#define all(v) v.begin(),v.end()
void boos() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int N = 2e5 + 100;
vector <int> g[N];
ll a[N],L,d[N][42];
int n,pr[N];
void dfs_build(int v,int p) {
	for(auto to : g[v]) {
		if(to == p)continue;
		pr[to] = v;
		dfs_build(to,v);
	}
}
void add(int x,int dist,ll w) {
	int v = x;
	int tek = 0;
	while(tek <= dist && v != -1) {
		d[v][dist - tek] = (d[v][dist - tek] * w) % L;
		tek++;
		v = pr[v];
	}
}
ll get(int x) {
	ll ans = a[x];
	int v = x,tek = 0;
	//cout << d[v][0] << endl;
	while(tek <= 40) {
		for(int j = tek + 1;j >= tek;j--)ans = (ans * d[v][j]) % L;
		tek++;
		if(pr[v] == -1) {
			for(int j = tek + 1;j <= 40;j++)ans = (ans * d[v][j]) % L;
			break;
		}
		v = pr[v];
	}
	return ans;
}
void solve() {
	cin >> n >> L;
	for(int i = 1;i <= n;i++) {
		pr[i] = -1;
		for(int j = 0;j <= 41;j++)d[i][j] = 1;
	}
	for(int i = 1;i < n;i++) {
		int x,y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	for(int i = 1;i <= n;i++)cin >> a[i];
	dfs_build(1,-1);
	int m;
	cin >> m;
	for(int i = 1;i <= m;i++) {
		int typ;
		cin >> typ;
		if(typ == 1) {
			int x,dist;
			ll w;
			cin >> x >> dist >> w;
			add(x,dist,w);
		}else {
			int x;
			cin >> x;
			cout << get(x) << en;
		}
	}
}

int main() {
	boos();
	int ttt;
	ttt = 1;
	while(ttt--) {
		solve();
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5424 KB Output is correct
6 Correct 5 ms 5420 KB Output is correct
7 Correct 5 ms 5424 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 3 ms 5028 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 5032 KB Output is correct
12 Correct 3 ms 5032 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5032 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 5028 KB Output is correct
24 Correct 3 ms 5048 KB Output is correct
25 Correct 3 ms 5040 KB Output is correct
26 Correct 3 ms 5024 KB Output is correct
27 Correct 3 ms 5028 KB Output is correct
28 Correct 3 ms 4948 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 506 ms 83000 KB Output is correct
3 Correct 381 ms 81600 KB Output is correct
4 Correct 516 ms 85316 KB Output is correct
5 Correct 466 ms 82128 KB Output is correct
6 Correct 347 ms 82036 KB Output is correct
7 Correct 362 ms 82436 KB Output is correct
8 Correct 286 ms 82968 KB Output is correct
9 Correct 711 ms 88656 KB Output is correct
10 Correct 421 ms 85748 KB Output is correct
11 Correct 596 ms 83896 KB Output is correct
12 Correct 358 ms 81460 KB Output is correct
13 Correct 240 ms 81216 KB Output is correct
14 Correct 247 ms 81600 KB Output is correct
15 Correct 249 ms 81272 KB Output is correct
16 Correct 252 ms 81304 KB Output is correct
17 Correct 287 ms 81868 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5032 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 5024 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 506 ms 83000 KB Output is correct
3 Correct 381 ms 81600 KB Output is correct
4 Correct 516 ms 85316 KB Output is correct
5 Correct 466 ms 82128 KB Output is correct
6 Correct 347 ms 82036 KB Output is correct
7 Correct 362 ms 82436 KB Output is correct
8 Correct 286 ms 82968 KB Output is correct
9 Correct 711 ms 88656 KB Output is correct
10 Correct 421 ms 85748 KB Output is correct
11 Correct 596 ms 83896 KB Output is correct
12 Correct 358 ms 81460 KB Output is correct
13 Correct 240 ms 81216 KB Output is correct
14 Correct 247 ms 81600 KB Output is correct
15 Correct 249 ms 81272 KB Output is correct
16 Correct 252 ms 81304 KB Output is correct
17 Correct 287 ms 81868 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 5032 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 5024 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 572 ms 83904 KB Output is correct
25 Correct 369 ms 80604 KB Output is correct
26 Correct 492 ms 86620 KB Output is correct
27 Correct 492 ms 82340 KB Output is correct
28 Correct 361 ms 82308 KB Output is correct
29 Correct 332 ms 82252 KB Output is correct
30 Correct 297 ms 82880 KB Output is correct
31 Correct 605 ms 87076 KB Output is correct
32 Correct 379 ms 84824 KB Output is correct
33 Correct 549 ms 83948 KB Output is correct
34 Correct 382 ms 80500 KB Output is correct
35 Correct 3 ms 5028 KB Output is correct
36 Correct 3 ms 4948 KB Output is correct
37 Correct 3 ms 5028 KB Output is correct
38 Correct 3 ms 5024 KB Output is correct
39 Correct 3 ms 4948 KB Output is correct
40 Correct 3 ms 5024 KB Output is correct
41 Correct 3 ms 4976 KB Output is correct
42 Correct 3 ms 4948 KB Output is correct
43 Correct 3 ms 4948 KB Output is correct
44 Correct 3 ms 4948 KB Output is correct
45 Correct 5 ms 5028 KB Output is correct
46 Correct 3 ms 4948 KB Output is correct
47 Correct 3 ms 4948 KB Output is correct
48 Correct 4 ms 5024 KB Output is correct
49 Correct 3 ms 4948 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 626 ms 85032 KB Output is correct
3 Correct 602 ms 83800 KB Output is correct
4 Correct 572 ms 84780 KB Output is correct
5 Correct 535 ms 81140 KB Output is correct
6 Correct 376 ms 81244 KB Output is correct
7 Correct 339 ms 81428 KB Output is correct
8 Correct 281 ms 81700 KB Output is correct
9 Correct 672 ms 84528 KB Output is correct
10 Correct 623 ms 85144 KB Output is correct
11 Correct 580 ms 81964 KB Output is correct
12 Correct 567 ms 82280 KB Output is correct
13 Correct 380 ms 82220 KB Output is correct
14 Correct 398 ms 82724 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 5032 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 671 ms 86000 KB Output is correct
3 Correct 675 ms 83536 KB Output is correct
4 Correct 588 ms 85568 KB Output is correct
5 Correct 512 ms 82164 KB Output is correct
6 Correct 390 ms 82636 KB Output is correct
7 Correct 475 ms 82648 KB Output is correct
8 Correct 354 ms 83068 KB Output is correct
9 Correct 723 ms 88556 KB Output is correct
10 Correct 619 ms 85292 KB Output is correct
11 Correct 641 ms 84012 KB Output is correct
12 Correct 537 ms 82476 KB Output is correct
13 Correct 363 ms 82332 KB Output is correct
14 Correct 396 ms 82736 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5024 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5424 KB Output is correct
6 Correct 5 ms 5420 KB Output is correct
7 Correct 5 ms 5424 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 3 ms 5028 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 5032 KB Output is correct
12 Correct 3 ms 5032 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 5032 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 5028 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 5028 KB Output is correct
24 Correct 3 ms 5048 KB Output is correct
25 Correct 3 ms 5040 KB Output is correct
26 Correct 3 ms 5024 KB Output is correct
27 Correct 3 ms 5028 KB Output is correct
28 Correct 3 ms 4948 KB Output is correct
29 Correct 2 ms 4948 KB Output is correct
30 Correct 506 ms 83000 KB Output is correct
31 Correct 381 ms 81600 KB Output is correct
32 Correct 516 ms 85316 KB Output is correct
33 Correct 466 ms 82128 KB Output is correct
34 Correct 347 ms 82036 KB Output is correct
35 Correct 362 ms 82436 KB Output is correct
36 Correct 286 ms 82968 KB Output is correct
37 Correct 711 ms 88656 KB Output is correct
38 Correct 421 ms 85748 KB Output is correct
39 Correct 596 ms 83896 KB Output is correct
40 Correct 358 ms 81460 KB Output is correct
41 Correct 240 ms 81216 KB Output is correct
42 Correct 247 ms 81600 KB Output is correct
43 Correct 249 ms 81272 KB Output is correct
44 Correct 252 ms 81304 KB Output is correct
45 Correct 287 ms 81868 KB Output is correct
46 Correct 3 ms 4948 KB Output is correct
47 Correct 3 ms 4948 KB Output is correct
48 Correct 3 ms 5032 KB Output is correct
49 Correct 3 ms 4948 KB Output is correct
50 Correct 3 ms 5024 KB Output is correct
51 Correct 3 ms 4948 KB Output is correct
52 Correct 572 ms 83904 KB Output is correct
53 Correct 369 ms 80604 KB Output is correct
54 Correct 492 ms 86620 KB Output is correct
55 Correct 492 ms 82340 KB Output is correct
56 Correct 361 ms 82308 KB Output is correct
57 Correct 332 ms 82252 KB Output is correct
58 Correct 297 ms 82880 KB Output is correct
59 Correct 605 ms 87076 KB Output is correct
60 Correct 379 ms 84824 KB Output is correct
61 Correct 549 ms 83948 KB Output is correct
62 Correct 382 ms 80500 KB Output is correct
63 Correct 3 ms 5028 KB Output is correct
64 Correct 3 ms 4948 KB Output is correct
65 Correct 3 ms 5028 KB Output is correct
66 Correct 3 ms 5024 KB Output is correct
67 Correct 3 ms 4948 KB Output is correct
68 Correct 3 ms 5024 KB Output is correct
69 Correct 3 ms 4976 KB Output is correct
70 Correct 3 ms 4948 KB Output is correct
71 Correct 3 ms 4948 KB Output is correct
72 Correct 3 ms 4948 KB Output is correct
73 Correct 5 ms 5028 KB Output is correct
74 Correct 3 ms 4948 KB Output is correct
75 Correct 3 ms 4948 KB Output is correct
76 Correct 4 ms 5024 KB Output is correct
77 Correct 3 ms 4948 KB Output is correct
78 Correct 3 ms 4948 KB Output is correct
79 Correct 626 ms 85032 KB Output is correct
80 Correct 602 ms 83800 KB Output is correct
81 Correct 572 ms 84780 KB Output is correct
82 Correct 535 ms 81140 KB Output is correct
83 Correct 376 ms 81244 KB Output is correct
84 Correct 339 ms 81428 KB Output is correct
85 Correct 281 ms 81700 KB Output is correct
86 Correct 672 ms 84528 KB Output is correct
87 Correct 623 ms 85144 KB Output is correct
88 Correct 580 ms 81964 KB Output is correct
89 Correct 567 ms 82280 KB Output is correct
90 Correct 380 ms 82220 KB Output is correct
91 Correct 398 ms 82724 KB Output is correct
92 Correct 3 ms 4948 KB Output is correct
93 Correct 3 ms 4948 KB Output is correct
94 Correct 4 ms 5032 KB Output is correct
95 Correct 3 ms 4948 KB Output is correct
96 Correct 3 ms 4948 KB Output is correct
97 Correct 3 ms 4948 KB Output is correct
98 Correct 671 ms 86000 KB Output is correct
99 Correct 675 ms 83536 KB Output is correct
100 Correct 588 ms 85568 KB Output is correct
101 Correct 512 ms 82164 KB Output is correct
102 Correct 390 ms 82636 KB Output is correct
103 Correct 475 ms 82648 KB Output is correct
104 Correct 354 ms 83068 KB Output is correct
105 Correct 723 ms 88556 KB Output is correct
106 Correct 619 ms 85292 KB Output is correct
107 Correct 641 ms 84012 KB Output is correct
108 Correct 537 ms 82476 KB Output is correct
109 Correct 363 ms 82332 KB Output is correct
110 Correct 396 ms 82736 KB Output is correct
111 Correct 3 ms 4948 KB Output is correct
112 Correct 3 ms 5024 KB Output is correct
113 Correct 3 ms 4948 KB Output is correct
114 Correct 4 ms 4948 KB Output is correct
115 Correct 3 ms 4948 KB Output is correct
116 Correct 568 ms 81808 KB Output is correct
117 Correct 565 ms 80384 KB Output is correct
118 Correct 586 ms 86568 KB Output is correct
119 Correct 512 ms 82156 KB Output is correct
120 Correct 444 ms 82128 KB Output is correct
121 Correct 453 ms 82448 KB Output is correct
122 Correct 365 ms 82868 KB Output is correct
123 Correct 673 ms 87508 KB Output is correct
124 Correct 700 ms 83292 KB Output is correct
125 Correct 617 ms 83240 KB Output is correct
126 Correct 617 ms 80596 KB Output is correct
127 Correct 559 ms 80460 KB Output is correct
128 Correct 397 ms 81304 KB Output is correct
129 Correct 417 ms 81692 KB Output is correct