답안 #589178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589178	2022-07-04T10:00:50 Z	Red_Inside	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	1583 ms	126468 KB

sprinkler

//
#include <bits/stdc++.h>
 
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define sortv(vv) sort(vv.begin(), vv.end())
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
 
using namespace std;
const int maxn=2e5+100,LOG=17, mod=1e9+7;
int block = 320, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
#define bt(i) (1 << (i))
#define int ll
const int inf=1e9+10;
#define y1 yy
#define prev pre
#define pii pair <int, int>
 
int n, q, anc[maxn], tin[maxn], tout[maxn], deep[maxn], sz[maxn], mem[maxn][42];
ll L, h[maxn];
vector <int> edge[maxn];
vector <pii> vec[maxn];
 
void dfs(int v, int pred = -1)
{
	tin[v] = ++timer;
	vec[deep[v]].pb({tin[v], v});
	for(auto to : edge[v])
	{
		if(to == pred) continue;
		deep[to] = deep[v] + 1;
		anc[to] = v;
		dfs(to, v);
	}
	tout[v] = timer;
}

 
inline void update(int x, int w, int d)
{
	if(d < 0) return;
	if(sz[deep[x] + d] == 0) return;
//	int L = lower_bound(all(vec[deep[x] + d]), mp(tin[x], 0)) - vec[deep[x] + d].begin() + 1;
//	int R = upper_bound(all(vec[deep[x] + d]), mp(tout[x], inf)) - vec[deep[x] + d].begin();
//	upd(1, 1, sz[deep[x] + d], L, R, w, deep[x] + d);
//s	cout << "UPDATE " << x << " " << w << " " << d << endl;
	mem[x][d] = mem[x][d] * (1ll * w) % L;
}
 
main()
{
	IOS
	cin >> n >> L;
	forn(1, i, n - 1)
	{
		int l, r;
		cin >> l >> r;
		edge[l].pb(r);
		edge[r].pb(l);
	}
	forn(1, i, n) cin >> h[i];
	forn(1, i, n)
	{
		forn(0, j, 40)
		{
			mem[i][j] = 1;
		}
	}
	deep[1] = 1;
	dfs(1);
	forn(1, i, n)
	{
		sz[i] = vec[i].size();
	}
	cin >> q;
	forn(1, i, q)
	{
		int ty;
		cin >> ty;
		if(ty == 1)
		{
			int x, d;
			int w;
			cin >> x >> d >> w;
			vector <int> ancs;
			int v = x;
			forn(0, iter, d)
			{
				ancs.pb(v);
				v = anc[v];
				if(v == 0) break;
			}
			forn(-d, a, d)
			{
				int b = (d + a) / 2;
				if((int)ancs.size() > b)
				{
//					cout << "START UPDATE " << ancs[b] << " " << a << " " << b << endl;
					update(ancs[b], w, b - a);
				}
				else
				{
//					cout << "START UPDATE " << ancs.back() << " " << a << " " << b << endl;
					update(ancs.back(), w, (int)ancs.size() - 1 - a);
				}
			}
		}
		else
		{
			int x;
			cin >> x;
//			int pos = lower_bound(all(vec[deep[x]]), mp(tin[x], x)) - vec[deep[x]].begin() + 1;
			ll ans = h[x];
			int v = x;
			forn(0, i, 40)
			{
				ans = ans * mem[v][i] % L;
				v = anc[v];
				if(v == 0) break;
			}
//			cout << h[x] << " " << get(1, 1, sz[deep[x]], pos, deep[x]) << endl;
			cout << ans << "\n";
		}
	}
}

Compilation message

sprinkler.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main()
      | ^~~~

Subtask #1

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9684 KB	Output is correct
2	Correct	6 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	6 ms	10196 KB	Output is correct
5	Correct	6 ms	10260 KB	Output is correct
6	Correct	5 ms	10256 KB	Output is correct
7	Correct	7 ms	10172 KB	Output is correct
8	Correct	6 ms	10256 KB	Output is correct
9	Correct	7 ms	9684 KB	Output is correct
10	Correct	5 ms	9784 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	5 ms	9744 KB	Output is correct
13	Correct	5 ms	9684 KB	Output is correct
14	Correct	6 ms	9684 KB	Output is correct
15	Correct	5 ms	9684 KB	Output is correct
16	Correct	5 ms	9740 KB	Output is correct
17	Correct	5 ms	9684 KB	Output is correct
18	Correct	5 ms	9684 KB	Output is correct
19	Correct	7 ms	9736 KB	Output is correct
20	Correct	6 ms	9744 KB	Output is correct
21	Correct	5 ms	9748 KB	Output is correct
22	Correct	5 ms	9684 KB	Output is correct
23	Correct	5 ms	9684 KB	Output is correct
24	Correct	8 ms	9744 KB	Output is correct
25	Correct	5 ms	9744 KB	Output is correct
26	Correct	5 ms	9684 KB	Output is correct
27	Correct	6 ms	9684 KB	Output is correct
28	Correct	5 ms	9684 KB	Output is correct

Subtask #2

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	587 ms	105812 KB	Output is correct
3	Correct	463 ms	104840 KB	Output is correct
4	Correct	631 ms	115248 KB	Output is correct
5	Correct	545 ms	104184 KB	Output is correct
6	Correct	399 ms	102516 KB	Output is correct
7	Correct	376 ms	103072 KB	Output is correct
8	Correct	335 ms	103224 KB	Output is correct
9	Correct	760 ms	123056 KB	Output is correct
10	Correct	520 ms	121324 KB	Output is correct
11	Correct	589 ms	104392 KB	Output is correct
12	Correct	453 ms	103964 KB	Output is correct
13	Correct	348 ms	103356 KB	Output is correct
14	Correct	296 ms	102664 KB	Output is correct
15	Correct	319 ms	101688 KB	Output is correct
16	Correct	314 ms	102908 KB	Output is correct
17	Correct	303 ms	102772 KB	Output is correct
18	Correct	5 ms	9684 KB	Output is correct
19	Correct	5 ms	9684 KB	Output is correct
20	Correct	6 ms	9684 KB	Output is correct
21	Correct	5 ms	9684 KB	Output is correct
22	Correct	5 ms	9768 KB	Output is correct

Subtask #3

29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	587 ms	105812 KB	Output is correct
3	Correct	463 ms	104840 KB	Output is correct
4	Correct	631 ms	115248 KB	Output is correct
5	Correct	545 ms	104184 KB	Output is correct
6	Correct	399 ms	102516 KB	Output is correct
7	Correct	376 ms	103072 KB	Output is correct
8	Correct	335 ms	103224 KB	Output is correct
9	Correct	760 ms	123056 KB	Output is correct
10	Correct	520 ms	121324 KB	Output is correct
11	Correct	589 ms	104392 KB	Output is correct
12	Correct	453 ms	103964 KB	Output is correct
13	Correct	348 ms	103356 KB	Output is correct
14	Correct	296 ms	102664 KB	Output is correct
15	Correct	319 ms	101688 KB	Output is correct
16	Correct	314 ms	102908 KB	Output is correct
17	Correct	303 ms	102772 KB	Output is correct
18	Correct	5 ms	9684 KB	Output is correct
19	Correct	5 ms	9684 KB	Output is correct
20	Correct	6 ms	9684 KB	Output is correct
21	Correct	5 ms	9684 KB	Output is correct
22	Correct	5 ms	9768 KB	Output is correct
23	Correct	5 ms	9764 KB	Output is correct
24	Correct	628 ms	104872 KB	Output is correct
25	Correct	447 ms	102388 KB	Output is correct
26	Correct	581 ms	121420 KB	Output is correct
27	Correct	522 ms	103632 KB	Output is correct
28	Correct	385 ms	102800 KB	Output is correct
29	Correct	403 ms	102648 KB	Output is correct
30	Correct	339 ms	102844 KB	Output is correct
31	Correct	662 ms	115992 KB	Output is correct
32	Correct	481 ms	119204 KB	Output is correct
33	Correct	645 ms	103784 KB	Output is correct
34	Correct	447 ms	102592 KB	Output is correct
35	Correct	6 ms	9684 KB	Output is correct
36	Correct	5 ms	9684 KB	Output is correct
37	Correct	5 ms	9744 KB	Output is correct
38	Correct	5 ms	9764 KB	Output is correct
39	Correct	5 ms	9740 KB	Output is correct
40	Correct	5 ms	9744 KB	Output is correct
41	Correct	5 ms	9736 KB	Output is correct
42	Correct	5 ms	9740 KB	Output is correct
43	Correct	7 ms	9684 KB	Output is correct
44	Correct	6 ms	9684 KB	Output is correct
45	Correct	6 ms	9732 KB	Output is correct
46	Correct	5 ms	9684 KB	Output is correct
47	Correct	5 ms	9684 KB	Output is correct
48	Correct	6 ms	9740 KB	Output is correct
49	Correct	6 ms	9684 KB	Output is correct

Subtask #4

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	821 ms	119728 KB	Output is correct
3	Correct	1358 ms	115992 KB	Output is correct
4	Correct	823 ms	117856 KB	Output is correct
5	Correct	718 ms	103340 KB	Output is correct
6	Correct	450 ms	102632 KB	Output is correct
7	Correct	432 ms	102636 KB	Output is correct
8	Correct	283 ms	102636 KB	Output is correct
9	Correct	744 ms	115836 KB	Output is correct
10	Correct	1399 ms	120164 KB	Output is correct
11	Correct	695 ms	104972 KB	Output is correct
12	Correct	1190 ms	104940 KB	Output is correct
13	Correct	746 ms	105764 KB	Output is correct
14	Correct	781 ms	108128 KB	Output is correct
15	Correct	6 ms	9864 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	5 ms	9684 KB	Output is correct
18	Correct	5 ms	9752 KB	Output is correct
19	Correct	5 ms	9684 KB	Output is correct

Subtask #5

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	806 ms	114144 KB	Output is correct
3	Correct	1378 ms	106224 KB	Output is correct
4	Correct	851 ms	109644 KB	Output is correct
5	Correct	826 ms	99624 KB	Output is correct
6	Correct	484 ms	103752 KB	Output is correct
7	Correct	478 ms	103704 KB	Output is correct
8	Correct	295 ms	103684 KB	Output is correct
9	Correct	791 ms	123044 KB	Output is correct
10	Correct	1441 ms	120484 KB	Output is correct
11	Correct	769 ms	105804 KB	Output is correct
12	Correct	1267 ms	104252 KB	Output is correct
13	Correct	814 ms	105808 KB	Output is correct
14	Correct	799 ms	108192 KB	Output is correct
15	Correct	5 ms	9684 KB	Output is correct
16	Correct	6 ms	9744 KB	Output is correct
17	Correct	5 ms	9684 KB	Output is correct
18	Correct	6 ms	9684 KB	Output is correct
19	Correct	7 ms	9684 KB	Output is correct

Subtask #6

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9684 KB	Output is correct
2	Correct	6 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	6 ms	10196 KB	Output is correct
5	Correct	6 ms	10260 KB	Output is correct
6	Correct	5 ms	10256 KB	Output is correct
7	Correct	7 ms	10172 KB	Output is correct
8	Correct	6 ms	10256 KB	Output is correct
9	Correct	7 ms	9684 KB	Output is correct
10	Correct	5 ms	9784 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	5 ms	9744 KB	Output is correct
13	Correct	5 ms	9684 KB	Output is correct
14	Correct	6 ms	9684 KB	Output is correct
15	Correct	5 ms	9684 KB	Output is correct
16	Correct	5 ms	9740 KB	Output is correct
17	Correct	5 ms	9684 KB	Output is correct
18	Correct	5 ms	9684 KB	Output is correct
19	Correct	7 ms	9736 KB	Output is correct
20	Correct	6 ms	9744 KB	Output is correct
21	Correct	5 ms	9748 KB	Output is correct
22	Correct	5 ms	9684 KB	Output is correct
23	Correct	5 ms	9684 KB	Output is correct
24	Correct	8 ms	9744 KB	Output is correct
25	Correct	5 ms	9744 KB	Output is correct
26	Correct	5 ms	9684 KB	Output is correct
27	Correct	6 ms	9684 KB	Output is correct
28	Correct	5 ms	9684 KB	Output is correct
29	Correct	5 ms	9684 KB	Output is correct
30	Correct	587 ms	105812 KB	Output is correct
31	Correct	463 ms	104840 KB	Output is correct
32	Correct	631 ms	115248 KB	Output is correct
33	Correct	545 ms	104184 KB	Output is correct
34	Correct	399 ms	102516 KB	Output is correct
35	Correct	376 ms	103072 KB	Output is correct
36	Correct	335 ms	103224 KB	Output is correct
37	Correct	760 ms	123056 KB	Output is correct
38	Correct	520 ms	121324 KB	Output is correct
39	Correct	589 ms	104392 KB	Output is correct
40	Correct	453 ms	103964 KB	Output is correct
41	Correct	348 ms	103356 KB	Output is correct
42	Correct	296 ms	102664 KB	Output is correct
43	Correct	319 ms	101688 KB	Output is correct
44	Correct	314 ms	102908 KB	Output is correct
45	Correct	303 ms	102772 KB	Output is correct
46	Correct	5 ms	9684 KB	Output is correct
47	Correct	5 ms	9684 KB	Output is correct
48	Correct	6 ms	9684 KB	Output is correct
49	Correct	5 ms	9684 KB	Output is correct
50	Correct	5 ms	9768 KB	Output is correct
51	Correct	5 ms	9764 KB	Output is correct
52	Correct	628 ms	104872 KB	Output is correct
53	Correct	447 ms	102388 KB	Output is correct
54	Correct	581 ms	121420 KB	Output is correct
55	Correct	522 ms	103632 KB	Output is correct
56	Correct	385 ms	102800 KB	Output is correct
57	Correct	403 ms	102648 KB	Output is correct
58	Correct	339 ms	102844 KB	Output is correct
59	Correct	662 ms	115992 KB	Output is correct
60	Correct	481 ms	119204 KB	Output is correct
61	Correct	645 ms	103784 KB	Output is correct
62	Correct	447 ms	102592 KB	Output is correct
63	Correct	6 ms	9684 KB	Output is correct
64	Correct	5 ms	9684 KB	Output is correct
65	Correct	5 ms	9744 KB	Output is correct
66	Correct	5 ms	9764 KB	Output is correct
67	Correct	5 ms	9740 KB	Output is correct
68	Correct	5 ms	9744 KB	Output is correct
69	Correct	5 ms	9736 KB	Output is correct
70	Correct	5 ms	9740 KB	Output is correct
71	Correct	7 ms	9684 KB	Output is correct
72	Correct	6 ms	9684 KB	Output is correct
73	Correct	6 ms	9732 KB	Output is correct
74	Correct	5 ms	9684 KB	Output is correct
75	Correct	5 ms	9684 KB	Output is correct
76	Correct	6 ms	9740 KB	Output is correct
77	Correct	6 ms	9684 KB	Output is correct
78	Correct	5 ms	9684 KB	Output is correct
79	Correct	821 ms	119728 KB	Output is correct
80	Correct	1358 ms	115992 KB	Output is correct
81	Correct	823 ms	117856 KB	Output is correct
82	Correct	718 ms	103340 KB	Output is correct
83	Correct	450 ms	102632 KB	Output is correct
84	Correct	432 ms	102636 KB	Output is correct
85	Correct	283 ms	102636 KB	Output is correct
86	Correct	744 ms	115836 KB	Output is correct
87	Correct	1399 ms	120164 KB	Output is correct
88	Correct	695 ms	104972 KB	Output is correct
89	Correct	1190 ms	104940 KB	Output is correct
90	Correct	746 ms	105764 KB	Output is correct
91	Correct	781 ms	108128 KB	Output is correct
92	Correct	6 ms	9864 KB	Output is correct
93	Correct	5 ms	9684 KB	Output is correct
94	Correct	5 ms	9684 KB	Output is correct
95	Correct	5 ms	9752 KB	Output is correct
96	Correct	5 ms	9684 KB	Output is correct
97	Correct	5 ms	9684 KB	Output is correct
98	Correct	806 ms	114144 KB	Output is correct
99	Correct	1378 ms	106224 KB	Output is correct
100	Correct	851 ms	109644 KB	Output is correct
101	Correct	826 ms	99624 KB	Output is correct
102	Correct	484 ms	103752 KB	Output is correct
103	Correct	478 ms	103704 KB	Output is correct
104	Correct	295 ms	103684 KB	Output is correct
105	Correct	791 ms	123044 KB	Output is correct
106	Correct	1441 ms	120484 KB	Output is correct
107	Correct	769 ms	105804 KB	Output is correct
108	Correct	1267 ms	104252 KB	Output is correct
109	Correct	814 ms	105808 KB	Output is correct
110	Correct	799 ms	108192 KB	Output is correct
111	Correct	5 ms	9684 KB	Output is correct
112	Correct	6 ms	9744 KB	Output is correct
113	Correct	5 ms	9684 KB	Output is correct
114	Correct	6 ms	9684 KB	Output is correct
115	Correct	7 ms	9684 KB	Output is correct
116	Correct	713 ms	106740 KB	Output is correct
117	Correct	1154 ms	109088 KB	Output is correct
118	Correct	911 ms	126468 KB	Output is correct
119	Correct	764 ms	108764 KB	Output is correct
120	Correct	516 ms	107548 KB	Output is correct
121	Correct	534 ms	108164 KB	Output is correct
122	Correct	374 ms	107996 KB	Output is correct
123	Correct	857 ms	123188 KB	Output is correct
124	Correct	1583 ms	119440 KB	Output is correct
125	Correct	749 ms	107792 KB	Output is correct
126	Correct	1286 ms	109252 KB	Output is correct
127	Correct	1368 ms	109832 KB	Output is correct
128	Correct	850 ms	109704 KB	Output is correct
129	Correct	957 ms	112264 KB	Output is correct