답안 #587282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587282	2022-07-01T15:09:48 Z	dutinmeow	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1588 ms	70888 KB

sprinkler

#include <bits/stdc++.h>
using namespace std;

#pragma region y_combinator

#ifndef Y_COMBINATOR_HPP
#define Y_COMBINATOR_HPP

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

#endif

#pragma endregion y_combinator

const int $D = 50;

int MOD;

struct mint {
	int v;

	mint() : v(0) {}

	mint(int _v) : v(_v % MOD) {}

	mint &operator+=(const mint &rhs) { 
		v += rhs.v;
		if (v >= MOD)
			v -= MOD;
		return *this;
	}

	mint &operator-=(const mint &rhs) { 
		v -= rhs.v;
		if (v < 0)
			v += MOD;
		return *this;
	}

	mint &operator*=(const mint &rhs) { 
		v = static_cast<long long>(v) * rhs.v % MOD;
		return *this;
	}
};

mint operator+(mint lhs, const mint &rhs) { return lhs += rhs; }

mint operator-(mint lhs, const mint &rhs) { return lhs -= rhs; }

mint operator*(mint lhs, const mint &rhs) { return lhs *= rhs; }

istream &operator>>(istream &is, mint &m) { return is >> m.v; }

ostream &operator<<(ostream &os, const mint &m) { return os << m.v; }

int main() {
	int N;
	cin >> N >> MOD;
	vector<vector<int>> T(N);
	for (int i = 1; i < N; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		T[u].push_back(v);
		T[v].push_back(u);
	}

	vector<int> par(N);
	par[0] = -1;

	y_combinator([&](auto dfs, int u) -> void {
		for (int v : T[u]) {
			if (v == par[u])
				continue;
			par[v] = u;
			dfs(v);
		}
	})(0);

	vector<mint> A(N);
	for (mint &a : A)
		cin >> a;
	
	vector<array<mint, $D>> L(N);
	for_each(L.begin(), L.end(), [](auto &t) { t.fill(mint(1)); });
	
	int Q;
	cin >> Q;
	while (Q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int s, d;
			mint v;
			cin >> s >> d >> v;
			s--;

			y_combinator([&](auto dfs, int u, int c) -> void {
				if (u == -1 || c > d)
					return;
				dfs(par[u], c + 1);
				if (u == 0) {	
					for (int i = 0; i <= d - c; i++)
						L[u][i] *= v;
				} else {
					if (d - c - 1 >= 0)
						L[u][d - c - 1] *= v;
					L[u][d - c] *= v;
				}
			})(s, 0);
		} else {
			int u;
			cin >> u;
			u--;
			mint ans = A[u];
			for (int d = 0; u != -1 && d < $D; d++) {
				ans *= L[u][d];
				u = par[u];
			}
			cout << ans << '\n';
		}
	}
}

Compilation message

sprinkler.cpp:4: warning: ignoring '#pragma region y_combinator' [-Wunknown-pragmas]
    4 | #pragma region y_combinator
      | 
sprinkler.cpp:29: warning: ignoring '#pragma endregion y_combinator' [-Wunknown-pragmas]
   29 | #pragma endregion y_combinator
      |

Subtask #1

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	3 ms	572 KB	Output is correct
5	Correct	3 ms	596 KB	Output is correct
6	Correct	3 ms	492 KB	Output is correct
7	Correct	3 ms	596 KB	Output is correct
8	Correct	3 ms	596 KB	Output is correct
9	Correct	2 ms	212 KB	Output is correct
10	Correct	2 ms	212 KB	Output is correct
11	Correct	2 ms	304 KB	Output is correct
12	Correct	2 ms	212 KB	Output is correct
13	Correct	2 ms	308 KB	Output is correct
14	Correct	2 ms	212 KB	Output is correct
15	Correct	2 ms	212 KB	Output is correct
16	Correct	2 ms	212 KB	Output is correct
17	Correct	2 ms	304 KB	Output is correct
18	Correct	2 ms	304 KB	Output is correct
19	Correct	2 ms	300 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	2 ms	212 KB	Output is correct
22	Correct	2 ms	304 KB	Output is correct
23	Correct	2 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	2 ms	212 KB	Output is correct
28	Correct	2 ms	212 KB	Output is correct

Subtask #2

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1401 ms	63852 KB	Output is correct
3	Correct	819 ms	64420 KB	Output is correct
4	Correct	1131 ms	68732 KB	Output is correct
5	Correct	1012 ms	64092 KB	Output is correct
6	Correct	886 ms	63588 KB	Output is correct
7	Correct	909 ms	64356 KB	Output is correct
8	Correct	791 ms	65016 KB	Output is correct
9	Correct	1447 ms	70880 KB	Output is correct
10	Correct	810 ms	70832 KB	Output is correct
11	Correct	1278 ms	63760 KB	Output is correct
12	Correct	806 ms	64320 KB	Output is correct
13	Correct	664 ms	64544 KB	Output is correct
14	Correct	671 ms	65060 KB	Output is correct
15	Correct	652 ms	64432 KB	Output is correct
16	Correct	663 ms	64988 KB	Output is correct
17	Correct	709 ms	65456 KB	Output is correct
18	Correct	2 ms	304 KB	Output is correct
19	Correct	2 ms	212 KB	Output is correct
20	Correct	2 ms	308 KB	Output is correct
21	Correct	2 ms	276 KB	Output is correct
22	Correct	2 ms	316 KB	Output is correct

Subtask #3

29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1401 ms	63852 KB	Output is correct
3	Correct	819 ms	64420 KB	Output is correct
4	Correct	1131 ms	68732 KB	Output is correct
5	Correct	1012 ms	64092 KB	Output is correct
6	Correct	886 ms	63588 KB	Output is correct
7	Correct	909 ms	64356 KB	Output is correct
8	Correct	791 ms	65016 KB	Output is correct
9	Correct	1447 ms	70880 KB	Output is correct
10	Correct	810 ms	70832 KB	Output is correct
11	Correct	1278 ms	63760 KB	Output is correct
12	Correct	806 ms	64320 KB	Output is correct
13	Correct	664 ms	64544 KB	Output is correct
14	Correct	671 ms	65060 KB	Output is correct
15	Correct	652 ms	64432 KB	Output is correct
16	Correct	663 ms	64988 KB	Output is correct
17	Correct	709 ms	65456 KB	Output is correct
18	Correct	2 ms	304 KB	Output is correct
19	Correct	2 ms	212 KB	Output is correct
20	Correct	2 ms	308 KB	Output is correct
21	Correct	2 ms	276 KB	Output is correct
22	Correct	2 ms	316 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1304 ms	63740 KB	Output is correct
25	Correct	827 ms	64356 KB	Output is correct
26	Correct	1129 ms	70884 KB	Output is correct
27	Correct	1051 ms	63956 KB	Output is correct
28	Correct	912 ms	64228 KB	Output is correct
29	Correct	873 ms	63892 KB	Output is correct
30	Correct	873 ms	64796 KB	Output is correct
31	Correct	1434 ms	68916 KB	Output is correct
32	Correct	831 ms	70888 KB	Output is correct
33	Correct	1316 ms	63776 KB	Output is correct
34	Correct	810 ms	64328 KB	Output is correct
35	Correct	1 ms	308 KB	Output is correct
36	Correct	2 ms	236 KB	Output is correct
37	Correct	2 ms	212 KB	Output is correct
38	Correct	2 ms	212 KB	Output is correct
39	Correct	2 ms	212 KB	Output is correct
40	Correct	1 ms	212 KB	Output is correct
41	Correct	2 ms	212 KB	Output is correct
42	Correct	2 ms	212 KB	Output is correct
43	Correct	1 ms	212 KB	Output is correct
44	Correct	2 ms	304 KB	Output is correct
45	Correct	1 ms	212 KB	Output is correct
46	Correct	1 ms	212 KB	Output is correct
47	Correct	1 ms	304 KB	Output is correct
48	Correct	2 ms	212 KB	Output is correct
49	Correct	1 ms	212 KB	Output is correct

Subtask #4

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1509 ms	67984 KB	Output is correct
3	Correct	1416 ms	66940 KB	Output is correct
4	Correct	1235 ms	66744 KB	Output is correct
5	Correct	1107 ms	61088 KB	Output is correct
6	Correct	1037 ms	61184 KB	Output is correct
7	Correct	887 ms	61408 KB	Output is correct
8	Correct	766 ms	61996 KB	Output is correct
9	Correct	1480 ms	66132 KB	Output is correct
10	Correct	1376 ms	67936 KB	Output is correct
11	Correct	1363 ms	60772 KB	Output is correct
12	Correct	1151 ms	61676 KB	Output is correct
13	Correct	926 ms	62540 KB	Output is correct
14	Correct	954 ms	63156 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	304 KB	Output is correct
17	Correct	2 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct

Subtask #5

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	296 KB	Output is correct
2	Correct	1588 ms	68236 KB	Output is correct
3	Correct	1423 ms	65548 KB	Output is correct
4	Correct	1224 ms	66960 KB	Output is correct
5	Correct	1158 ms	62688 KB	Output is correct
6	Correct	949 ms	62828 KB	Output is correct
7	Correct	891 ms	62620 KB	Output is correct
8	Correct	769 ms	62888 KB	Output is correct
9	Correct	1522 ms	70132 KB	Output is correct
10	Correct	1492 ms	68764 KB	Output is correct
11	Correct	1359 ms	63460 KB	Output is correct
12	Correct	1180 ms	62000 KB	Output is correct
13	Correct	945 ms	62632 KB	Output is correct
14	Correct	897 ms	63292 KB	Output is correct
15	Correct	2 ms	212 KB	Output is correct
16	Correct	2 ms	212 KB	Output is correct
17	Correct	1 ms	304 KB	Output is correct
18	Correct	2 ms	308 KB	Output is correct
19	Correct	2 ms	212 KB	Output is correct

Subtask #6

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	3 ms	572 KB	Output is correct
5	Correct	3 ms	596 KB	Output is correct
6	Correct	3 ms	492 KB	Output is correct
7	Correct	3 ms	596 KB	Output is correct
8	Correct	3 ms	596 KB	Output is correct
9	Correct	2 ms	212 KB	Output is correct
10	Correct	2 ms	212 KB	Output is correct
11	Correct	2 ms	304 KB	Output is correct
12	Correct	2 ms	212 KB	Output is correct
13	Correct	2 ms	308 KB	Output is correct
14	Correct	2 ms	212 KB	Output is correct
15	Correct	2 ms	212 KB	Output is correct
16	Correct	2 ms	212 KB	Output is correct
17	Correct	2 ms	304 KB	Output is correct
18	Correct	2 ms	304 KB	Output is correct
19	Correct	2 ms	300 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	2 ms	212 KB	Output is correct
22	Correct	2 ms	304 KB	Output is correct
23	Correct	2 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	2 ms	212 KB	Output is correct
28	Correct	2 ms	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1401 ms	63852 KB	Output is correct
31	Correct	819 ms	64420 KB	Output is correct
32	Correct	1131 ms	68732 KB	Output is correct
33	Correct	1012 ms	64092 KB	Output is correct
34	Correct	886 ms	63588 KB	Output is correct
35	Correct	909 ms	64356 KB	Output is correct
36	Correct	791 ms	65016 KB	Output is correct
37	Correct	1447 ms	70880 KB	Output is correct
38	Correct	810 ms	70832 KB	Output is correct
39	Correct	1278 ms	63760 KB	Output is correct
40	Correct	806 ms	64320 KB	Output is correct
41	Correct	664 ms	64544 KB	Output is correct
42	Correct	671 ms	65060 KB	Output is correct
43	Correct	652 ms	64432 KB	Output is correct
44	Correct	663 ms	64988 KB	Output is correct
45	Correct	709 ms	65456 KB	Output is correct
46	Correct	2 ms	304 KB	Output is correct
47	Correct	2 ms	212 KB	Output is correct
48	Correct	2 ms	308 KB	Output is correct
49	Correct	2 ms	276 KB	Output is correct
50	Correct	2 ms	316 KB	Output is correct
51	Correct	1 ms	212 KB	Output is correct
52	Correct	1304 ms	63740 KB	Output is correct
53	Correct	827 ms	64356 KB	Output is correct
54	Correct	1129 ms	70884 KB	Output is correct
55	Correct	1051 ms	63956 KB	Output is correct
56	Correct	912 ms	64228 KB	Output is correct
57	Correct	873 ms	63892 KB	Output is correct
58	Correct	873 ms	64796 KB	Output is correct
59	Correct	1434 ms	68916 KB	Output is correct
60	Correct	831 ms	70888 KB	Output is correct
61	Correct	1316 ms	63776 KB	Output is correct
62	Correct	810 ms	64328 KB	Output is correct
63	Correct	1 ms	308 KB	Output is correct
64	Correct	2 ms	236 KB	Output is correct
65	Correct	2 ms	212 KB	Output is correct
66	Correct	2 ms	212 KB	Output is correct
67	Correct	2 ms	212 KB	Output is correct
68	Correct	1 ms	212 KB	Output is correct
69	Correct	2 ms	212 KB	Output is correct
70	Correct	2 ms	212 KB	Output is correct
71	Correct	1 ms	212 KB	Output is correct
72	Correct	2 ms	304 KB	Output is correct
73	Correct	1 ms	212 KB	Output is correct
74	Correct	1 ms	212 KB	Output is correct
75	Correct	1 ms	304 KB	Output is correct
76	Correct	2 ms	212 KB	Output is correct
77	Correct	1 ms	212 KB	Output is correct
78	Correct	1 ms	212 KB	Output is correct
79	Correct	1509 ms	67984 KB	Output is correct
80	Correct	1416 ms	66940 KB	Output is correct
81	Correct	1235 ms	66744 KB	Output is correct
82	Correct	1107 ms	61088 KB	Output is correct
83	Correct	1037 ms	61184 KB	Output is correct
84	Correct	887 ms	61408 KB	Output is correct
85	Correct	766 ms	61996 KB	Output is correct
86	Correct	1480 ms	66132 KB	Output is correct
87	Correct	1376 ms	67936 KB	Output is correct
88	Correct	1363 ms	60772 KB	Output is correct
89	Correct	1151 ms	61676 KB	Output is correct
90	Correct	926 ms	62540 KB	Output is correct
91	Correct	954 ms	63156 KB	Output is correct
92	Correct	1 ms	212 KB	Output is correct
93	Correct	1 ms	304 KB	Output is correct
94	Correct	2 ms	212 KB	Output is correct
95	Correct	1 ms	212 KB	Output is correct
96	Correct	1 ms	212 KB	Output is correct
97	Correct	0 ms	296 KB	Output is correct
98	Correct	1588 ms	68236 KB	Output is correct
99	Correct	1423 ms	65548 KB	Output is correct
100	Correct	1224 ms	66960 KB	Output is correct
101	Correct	1158 ms	62688 KB	Output is correct
102	Correct	949 ms	62828 KB	Output is correct
103	Correct	891 ms	62620 KB	Output is correct
104	Correct	769 ms	62888 KB	Output is correct
105	Correct	1522 ms	70132 KB	Output is correct
106	Correct	1492 ms	68764 KB	Output is correct
107	Correct	1359 ms	63460 KB	Output is correct
108	Correct	1180 ms	62000 KB	Output is correct
109	Correct	945 ms	62632 KB	Output is correct
110	Correct	897 ms	63292 KB	Output is correct
111	Correct	2 ms	212 KB	Output is correct
112	Correct	2 ms	212 KB	Output is correct
113	Correct	1 ms	304 KB	Output is correct
114	Correct	2 ms	308 KB	Output is correct
115	Correct	2 ms	212 KB	Output is correct
116	Correct	1353 ms	61752 KB	Output is correct
117	Correct	1355 ms	64516 KB	Output is correct
118	Correct	1297 ms	70764 KB	Output is correct
119	Correct	1248 ms	64192 KB	Output is correct
120	Correct	971 ms	63660 KB	Output is correct
121	Correct	985 ms	64508 KB	Output is correct
122	Correct	873 ms	64828 KB	Output is correct
123	Correct	1565 ms	69556 KB	Output is correct
124	Correct	1480 ms	68544 KB	Output is correct
125	Correct	1437 ms	63072 KB	Output is correct
126	Correct	1389 ms	64228 KB	Output is correct
127	Correct	1291 ms	64876 KB	Output is correct
128	Correct	1113 ms	65484 KB	Output is correct
129	Correct	1126 ms	66148 KB	Output is correct