oj.uz

Submission #615491

# Submission time Handle Problem Language Result Execution time Memory
615491 2022-07-31T09:53:46 Z 장태환(#8493) Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 71240 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
int N, L;
int qs, qe, n;
struct st
{
	vector<long long>r;
	int treeN;
	void init(int cnt)
	{
		for (treeN = 1; treeN < cnt; treeN *= 2);
		r.resize(2 * treeN + 3, 1);
	}
	void upd(int s, int e, int i = 1)
	{
		if (s > qe || qs > e)
			return;
		if (qs <= s && e <= qe)
		{
			r[i] *= n;
			if (r[i] >= L)
				r[i] %= L;
			return;
		}
		upd(s, (s + e) / 2, i * 2);
		upd((s + e) / 2 + 1, e, i * 2 + 1);
	}
	int ge(int qs, int qe, int n, int i = 1)
	{
		if (qs == qe)
		{
			return r[i];
		}
		int m = (qs + qe) / 2;
		if (n > m)
		{
			return r[i] * ge(m + 1, qe, n, i * 2 + 1) % L;
		}
		else
		{
			return r[i] * ge(qs, m, n, i * 2) % L;
		}
	}
}arr[200100];
int d[201000];
int pos[200100];
int par[200100];
int st[201000];
int en[200100];
int c;
vector<int>li[201000];
vector<pair<int, int>>dl[200100];
vector<int>dl2[200100];
void dfs(int n, int p = 0)
{
	st[n] = ++c;
	dl[d[n]].push_back({ st[n],n });
	dl2[d[n]].push_back(st[n]);
	int i;
	for (i = 0; i < li[n].size(); i++)
	{
		if (li[n][i] == p)
			continue;
		par[li[n][i]] = n;
		d[li[n][i]] = d[n] + 1;
		dfs(li[n][i], n);
	}
	en[n] = c;
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> L;
	int i;
	for (i = 1; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		li[a].push_back(b);
		li[b].push_back(a);
	}
	dfs(1);
	for (i = 0; i <= N; i++)
	{
		arr[i].init(dl[i].size());
		int j;
		for (j = 0; j < dl[i].size(); j++)
		{
			pos[dl[i][j].second] = j;
		}
	}
	for (i = 1; i <= N; i++)
	{
		int a;
		cin >> a;
		arr[d[i]].r[pos[i] + arr[d[i]].treeN] = a;
	}
	int Q;
	cin >> Q;
	while (Q--)
	{
		int a;
		cin >> a;
		if (a == 1)
		{
			int b, c, w;
			cin >> b >> c >> w;
			int j;
			int dp = d[b];
			int cp = b;
			for (j = dp + c; j >= dp - c; j--)
			{
				if (j + dp - d[cp] * 2 + 2 <= c && cp != 1)
				{
					cp = par[cp];
				}
				if (j < 0)
					break;
				int lp = lower_bound(dl2[j].begin(), dl2[j].end(), st[cp]) - dl2[j].begin();
				if (lp != dl2[j].size() && dl2[j][lp] <= en[cp])
				{
					int rp = lower_bound(dl2[j].begin()+lp, dl2[j].end(), en[cp] + 1) - dl2[j].begin() - 1;
					qs = lp;
					qe = rp;
					n = w;
					arr[j].upd(0, arr[j].treeN - 1);
				}

			}
		}
		else
		{
			int b;
			cin >> b;
			cout << arr[d[b]].ge(0, arr[d[b]].treeN - 1, pos[b]) << '\n';
		}
	}

}

Compilation message

sprinkler.cpp: In function 'void dfs(int, int)':
sprinkler.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (i = 0; i < li[n].size(); i++)
      |              ~~^~~~~~~~~~~~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for (j = 0; j < dl[i].size(); j++)
      |               ~~^~~~~~~~~~~~~~
sprinkler.cpp:124:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     if (lp != dl2[j].size() && dl2[j][lp] <= en[cp])
      |         ~~~^~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20692 KB Output is correct
2 Correct 11 ms 20628 KB Output is correct
3 Correct 10 ms 20732 KB Output is correct
4 Correct 14 ms 20872 KB Output is correct
5 Correct 19 ms 20792 KB Output is correct
6 Correct 14 ms 20784 KB Output is correct
7 Correct 14 ms 20820 KB Output is correct
8 Correct 17 ms 20808 KB Output is correct
9 Correct 13 ms 20692 KB Output is correct
10 Correct 13 ms 20704 KB Output is correct
11 Correct 15 ms 20744 KB Output is correct
12 Correct 12 ms 20684 KB Output is correct
13 Correct 13 ms 20712 KB Output is correct
14 Correct 12 ms 20628 KB Output is correct
15 Correct 14 ms 20692 KB Output is correct
16 Correct 12 ms 20660 KB Output is correct
17 Correct 11 ms 20692 KB Output is correct
18 Correct 13 ms 20836 KB Output is correct
19 Correct 11 ms 20680 KB Output is correct
20 Correct 13 ms 20692 KB Output is correct
21 Correct 12 ms 20712 KB Output is correct
22 Correct 13 ms 20684 KB Output is correct
23 Correct 12 ms 20740 KB Output is correct
24 Correct 11 ms 20692 KB Output is correct
25 Correct 11 ms 20692 KB Output is correct
26 Correct 11 ms 20632 KB Output is correct
27 Correct 11 ms 20692 KB Output is correct
28 Correct 14 ms 20692 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20712 KB Output is correct
2 Correct 509 ms 51904 KB Output is correct
3 Correct 666 ms 48940 KB Output is correct
4 Correct 528 ms 61500 KB Output is correct
5 Correct 460 ms 50524 KB Output is correct
6 Correct 604 ms 49628 KB Output is correct
7 Correct 627 ms 49616 KB Output is correct
8 Correct 501 ms 49400 KB Output is correct
9 Correct 505 ms 71240 KB Output is correct
10 Correct 505 ms 66168 KB Output is correct
11 Correct 364 ms 51748 KB Output is correct
12 Correct 604 ms 48844 KB Output is correct
13 Correct 365 ms 48532 KB Output is correct
14 Correct 414 ms 48996 KB Output is correct
15 Correct 407 ms 48704 KB Output is correct
16 Correct 471 ms 48768 KB Output is correct
17 Correct 522 ms 48756 KB Output is correct
18 Correct 11 ms 20692 KB Output is correct
19 Correct 12 ms 20692 KB Output is correct
20 Correct 12 ms 20692 KB Output is correct
21 Correct 12 ms 20700 KB Output is correct
22 Correct 14 ms 20684 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20712 KB Output is correct
2 Correct 509 ms 51904 KB Output is correct
3 Correct 666 ms 48940 KB Output is correct
4 Correct 528 ms 61500 KB Output is correct
5 Correct 460 ms 50524 KB Output is correct
6 Correct 604 ms 49628 KB Output is correct
7 Correct 627 ms 49616 KB Output is correct
8 Correct 501 ms 49400 KB Output is correct
9 Correct 505 ms 71240 KB Output is correct
10 Correct 505 ms 66168 KB Output is correct
11 Correct 364 ms 51748 KB Output is correct
12 Correct 604 ms 48844 KB Output is correct
13 Correct 365 ms 48532 KB Output is correct
14 Correct 414 ms 48996 KB Output is correct
15 Correct 407 ms 48704 KB Output is correct
16 Correct 471 ms 48768 KB Output is correct
17 Correct 522 ms 48756 KB Output is correct
18 Correct 11 ms 20692 KB Output is correct
19 Correct 12 ms 20692 KB Output is correct
20 Correct 12 ms 20692 KB Output is correct
21 Correct 12 ms 20700 KB Output is correct
22 Correct 14 ms 20684 KB Output is correct
23 Correct 14 ms 20652 KB Output is correct
24 Correct 407 ms 51680 KB Output is correct
25 Correct 735 ms 48672 KB Output is correct
26 Correct 508 ms 68556 KB Output is correct
27 Correct 570 ms 50276 KB Output is correct
28 Correct 583 ms 49852 KB Output is correct
29 Correct 626 ms 50148 KB Output is correct
30 Correct 420 ms 49400 KB Output is correct
31 Correct 437 ms 63860 KB Output is correct
32 Correct 552 ms 66108 KB Output is correct
33 Correct 396 ms 51916 KB Output is correct
34 Correct 716 ms 48468 KB Output is correct
35 Correct 12 ms 20692 KB Output is correct
36 Correct 13 ms 20692 KB Output is correct
37 Correct 11 ms 20692 KB Output is correct
38 Correct 12 ms 20732 KB Output is correct
39 Correct 11 ms 20692 KB Output is correct
40 Correct 11 ms 20692 KB Output is correct
41 Correct 13 ms 20692 KB Output is correct
42 Correct 15 ms 20684 KB Output is correct
43 Correct 11 ms 20740 KB Output is correct
44 Correct 12 ms 20692 KB Output is correct
45 Correct 12 ms 20688 KB Output is correct
46 Correct 13 ms 20692 KB Output is correct
47 Correct 11 ms 20700 KB Output is correct
48 Correct 13 ms 20648 KB Output is correct
49 Correct 14 ms 20692 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20660 KB Output is correct
2 Correct 547 ms 68224 KB Output is correct
3 Correct 1893 ms 61572 KB Output is correct
4 Correct 957 ms 63216 KB Output is correct
5 Correct 2138 ms 48660 KB Output is correct
6 Correct 1581 ms 48112 KB Output is correct
7 Correct 928 ms 48764 KB Output is correct
8 Correct 349 ms 47884 KB Output is correct
9 Correct 657 ms 61284 KB Output is correct
10 Correct 1554 ms 65544 KB Output is correct
11 Correct 1168 ms 49500 KB Output is correct
12 Execution timed out 4058 ms 48276 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20732 KB Output is correct
2 Correct 609 ms 62840 KB Output is correct
3 Correct 2071 ms 56524 KB Output is correct
4 Correct 904 ms 60168 KB Output is correct
5 Correct 2297 ms 50288 KB Output is correct
6 Correct 1727 ms 49940 KB Output is correct
7 Correct 1452 ms 49148 KB Output is correct
8 Correct 366 ms 49304 KB Output is correct
9 Correct 769 ms 69400 KB Output is correct
10 Correct 1710 ms 66536 KB Output is correct
11 Correct 1163 ms 51700 KB Output is correct
12 Execution timed out 4053 ms 48720 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20692 KB Output is correct
2 Correct 11 ms 20628 KB Output is correct
3 Correct 10 ms 20732 KB Output is correct
4 Correct 14 ms 20872 KB Output is correct
5 Correct 19 ms 20792 KB Output is correct
6 Correct 14 ms 20784 KB Output is correct
7 Correct 14 ms 20820 KB Output is correct
8 Correct 17 ms 20808 KB Output is correct
9 Correct 13 ms 20692 KB Output is correct
10 Correct 13 ms 20704 KB Output is correct
11 Correct 15 ms 20744 KB Output is correct
12 Correct 12 ms 20684 KB Output is correct
13 Correct 13 ms 20712 KB Output is correct
14 Correct 12 ms 20628 KB Output is correct
15 Correct 14 ms 20692 KB Output is correct
16 Correct 12 ms 20660 KB Output is correct
17 Correct 11 ms 20692 KB Output is correct
18 Correct 13 ms 20836 KB Output is correct
19 Correct 11 ms 20680 KB Output is correct
20 Correct 13 ms 20692 KB Output is correct
21 Correct 12 ms 20712 KB Output is correct
22 Correct 13 ms 20684 KB Output is correct
23 Correct 12 ms 20740 KB Output is correct
24 Correct 11 ms 20692 KB Output is correct
25 Correct 11 ms 20692 KB Output is correct
26 Correct 11 ms 20632 KB Output is correct
27 Correct 11 ms 20692 KB Output is correct
28 Correct 14 ms 20692 KB Output is correct
29 Correct 14 ms 20712 KB Output is correct
30 Correct 509 ms 51904 KB Output is correct
31 Correct 666 ms 48940 KB Output is correct
32 Correct 528 ms 61500 KB Output is correct
33 Correct 460 ms 50524 KB Output is correct
34 Correct 604 ms 49628 KB Output is correct
35 Correct 627 ms 49616 KB Output is correct
36 Correct 501 ms 49400 KB Output is correct
37 Correct 505 ms 71240 KB Output is correct
38 Correct 505 ms 66168 KB Output is correct
39 Correct 364 ms 51748 KB Output is correct
40 Correct 604 ms 48844 KB Output is correct
41 Correct 365 ms 48532 KB Output is correct
42 Correct 414 ms 48996 KB Output is correct
43 Correct 407 ms 48704 KB Output is correct
44 Correct 471 ms 48768 KB Output is correct
45 Correct 522 ms 48756 KB Output is correct
46 Correct 11 ms 20692 KB Output is correct
47 Correct 12 ms 20692 KB Output is correct
48 Correct 12 ms 20692 KB Output is correct
49 Correct 12 ms 20700 KB Output is correct
50 Correct 14 ms 20684 KB Output is correct
51 Correct 14 ms 20652 KB Output is correct
52 Correct 407 ms 51680 KB Output is correct
53 Correct 735 ms 48672 KB Output is correct
54 Correct 508 ms 68556 KB Output is correct
55 Correct 570 ms 50276 KB Output is correct
56 Correct 583 ms 49852 KB Output is correct
57 Correct 626 ms 50148 KB Output is correct
58 Correct 420 ms 49400 KB Output is correct
59 Correct 437 ms 63860 KB Output is correct
60 Correct 552 ms 66108 KB Output is correct
61 Correct 396 ms 51916 KB Output is correct
62 Correct 716 ms 48468 KB Output is correct
63 Correct 12 ms 20692 KB Output is correct
64 Correct 13 ms 20692 KB Output is correct
65 Correct 11 ms 20692 KB Output is correct
66 Correct 12 ms 20732 KB Output is correct
67 Correct 11 ms 20692 KB Output is correct
68 Correct 11 ms 20692 KB Output is correct
69 Correct 13 ms 20692 KB Output is correct
70 Correct 15 ms 20684 KB Output is correct
71 Correct 11 ms 20740 KB Output is correct
72 Correct 12 ms 20692 KB Output is correct
73 Correct 12 ms 20688 KB Output is correct
74 Correct 13 ms 20692 KB Output is correct
75 Correct 11 ms 20700 KB Output is correct
76 Correct 13 ms 20648 KB Output is correct
77 Correct 14 ms 20692 KB Output is correct
78 Correct 12 ms 20660 KB Output is correct
79 Correct 547 ms 68224 KB Output is correct
80 Correct 1893 ms 61572 KB Output is correct
81 Correct 957 ms 63216 KB Output is correct
82 Correct 2138 ms 48660 KB Output is correct
83 Correct 1581 ms 48112 KB Output is correct
84 Correct 928 ms 48764 KB Output is correct
85 Correct 349 ms 47884 KB Output is correct
86 Correct 657 ms 61284 KB Output is correct
87 Correct 1554 ms 65544 KB Output is correct
88 Correct 1168 ms 49500 KB Output is correct
89 Execution timed out 4058 ms 48276 KB Time limit exceeded
90 Halted 0 ms 0 KB -