oj.uz

Submission #615426

# Submission time Handle Problem Language Result Execution time Memory
615426 2022-07-31T09:07:09 Z 장태환(#8493) Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 71304 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#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;
			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);
	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();
				int rp = lower_bound(dl2[j].begin(), dl2[j].end(), en[cp] + 1) - dl2[j].begin() - 1;
				if (lp <= rp)
				{
					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:90: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]
   90 |   for (j = 0; j < dl[i].size(); j++)
      |               ~~^~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20692 KB Output is correct
2 Correct 15 ms 20692 KB Output is correct
3 Correct 11 ms 20692 KB Output is correct
4 Correct 12 ms 20820 KB Output is correct
5 Correct 12 ms 20820 KB Output is correct
6 Correct 12 ms 20820 KB Output is correct
7 Correct 12 ms 20880 KB Output is correct
8 Correct 12 ms 20872 KB Output is correct
9 Correct 11 ms 20692 KB Output is correct
10 Correct 14 ms 20736 KB Output is correct
11 Correct 12 ms 20692 KB Output is correct
12 Correct 15 ms 20668 KB Output is correct
13 Correct 11 ms 20736 KB Output is correct
14 Correct 11 ms 20712 KB Output is correct
15 Correct 14 ms 20692 KB Output is correct
16 Correct 14 ms 20748 KB Output is correct
17 Correct 13 ms 20692 KB Output is correct
18 Correct 11 ms 20692 KB Output is correct
19 Correct 11 ms 20640 KB Output is correct
20 Correct 12 ms 20640 KB Output is correct
21 Correct 12 ms 20692 KB Output is correct
22 Correct 13 ms 20692 KB Output is correct
23 Correct 11 ms 20736 KB Output is correct
24 Correct 10 ms 20692 KB Output is correct
25 Correct 13 ms 20712 KB Output is correct
26 Correct 11 ms 20628 KB Output is correct
27 Correct 13 ms 20744 KB Output is correct
28 Correct 11 ms 20676 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20632 KB Output is correct
2 Correct 438 ms 51788 KB Output is correct
3 Correct 660 ms 48816 KB Output is correct
4 Correct 512 ms 61384 KB Output is correct
5 Correct 493 ms 50412 KB Output is correct
6 Correct 603 ms 49708 KB Output is correct
7 Correct 525 ms 49632 KB Output is correct
8 Correct 467 ms 49444 KB Output is correct
9 Correct 463 ms 71304 KB Output is correct
10 Correct 516 ms 66124 KB Output is correct
11 Correct 371 ms 51660 KB Output is correct
12 Correct 632 ms 48712 KB Output is correct
13 Correct 346 ms 48516 KB Output is correct
14 Correct 405 ms 49212 KB Output is correct
15 Correct 426 ms 48716 KB Output is correct
16 Correct 437 ms 48784 KB Output is correct
17 Correct 550 ms 48828 KB Output is correct
18 Correct 14 ms 20708 KB Output is correct
19 Correct 13 ms 20708 KB Output is correct
20 Correct 11 ms 20740 KB Output is correct
21 Correct 14 ms 20692 KB Output is correct
22 Correct 11 ms 20692 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 20632 KB Output is correct
2 Correct 438 ms 51788 KB Output is correct
3 Correct 660 ms 48816 KB Output is correct
4 Correct 512 ms 61384 KB Output is correct
5 Correct 493 ms 50412 KB Output is correct
6 Correct 603 ms 49708 KB Output is correct
7 Correct 525 ms 49632 KB Output is correct
8 Correct 467 ms 49444 KB Output is correct
9 Correct 463 ms 71304 KB Output is correct
10 Correct 516 ms 66124 KB Output is correct
11 Correct 371 ms 51660 KB Output is correct
12 Correct 632 ms 48712 KB Output is correct
13 Correct 346 ms 48516 KB Output is correct
14 Correct 405 ms 49212 KB Output is correct
15 Correct 426 ms 48716 KB Output is correct
16 Correct 437 ms 48784 KB Output is correct
17 Correct 550 ms 48828 KB Output is correct
18 Correct 14 ms 20708 KB Output is correct
19 Correct 13 ms 20708 KB Output is correct
20 Correct 11 ms 20740 KB Output is correct
21 Correct 14 ms 20692 KB Output is correct
22 Correct 11 ms 20692 KB Output is correct
23 Correct 12 ms 20692 KB Output is correct
24 Correct 432 ms 51684 KB Output is correct
25 Correct 809 ms 48784 KB Output is correct
26 Correct 520 ms 68608 KB Output is correct
27 Correct 552 ms 50280 KB Output is correct
28 Correct 616 ms 49816 KB Output is correct
29 Correct 591 ms 50120 KB Output is correct
30 Correct 390 ms 49408 KB Output is correct
31 Correct 434 ms 63800 KB Output is correct
32 Correct 605 ms 66172 KB Output is correct
33 Correct 452 ms 52152 KB Output is correct
34 Correct 793 ms 48560 KB Output is correct
35 Correct 11 ms 20692 KB Output is correct
36 Correct 12 ms 20692 KB Output is correct
37 Correct 11 ms 20692 KB Output is correct
38 Correct 11 ms 20792 KB Output is correct
39 Correct 11 ms 20692 KB Output is correct
40 Correct 14 ms 20732 KB Output is correct
41 Correct 12 ms 20696 KB Output is correct
42 Correct 11 ms 20692 KB Output is correct
43 Correct 11 ms 20692 KB Output is correct
44 Correct 13 ms 20692 KB Output is correct
45 Correct 11 ms 20692 KB Output is correct
46 Correct 11 ms 20692 KB Output is correct
47 Correct 11 ms 20732 KB Output is correct
48 Correct 12 ms 20736 KB Output is correct
49 Correct 11 ms 20676 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20692 KB Output is correct
2 Correct 547 ms 68128 KB Output is correct
3 Correct 1793 ms 61560 KB Output is correct
4 Correct 869 ms 63020 KB Output is correct
5 Correct 2212 ms 48664 KB Output is correct
6 Correct 1672 ms 48216 KB Output is correct
7 Correct 1042 ms 48824 KB Output is correct
8 Correct 330 ms 47916 KB Output is correct
9 Correct 555 ms 61256 KB Output is correct
10 Correct 1660 ms 65408 KB Output is correct
11 Correct 1053 ms 49260 KB Output is correct
12 Execution timed out 4091 ms 48288 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20692 KB Output is correct
2 Correct 617 ms 62876 KB Output is correct
3 Correct 2028 ms 56328 KB Output is correct
4 Correct 876 ms 60200 KB Output is correct
5 Correct 2255 ms 50392 KB Output is correct
6 Correct 1481 ms 49864 KB Output is correct
7 Correct 1037 ms 49232 KB Output is correct
8 Correct 369 ms 49204 KB Output is correct
9 Correct 651 ms 69468 KB Output is correct
10 Correct 1513 ms 66504 KB Output is correct
11 Correct 1119 ms 51532 KB Output is correct
12 Execution timed out 4085 ms 48536 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20692 KB Output is correct
2 Correct 15 ms 20692 KB Output is correct
3 Correct 11 ms 20692 KB Output is correct
4 Correct 12 ms 20820 KB Output is correct
5 Correct 12 ms 20820 KB Output is correct
6 Correct 12 ms 20820 KB Output is correct
7 Correct 12 ms 20880 KB Output is correct
8 Correct 12 ms 20872 KB Output is correct
9 Correct 11 ms 20692 KB Output is correct
10 Correct 14 ms 20736 KB Output is correct
11 Correct 12 ms 20692 KB Output is correct
12 Correct 15 ms 20668 KB Output is correct
13 Correct 11 ms 20736 KB Output is correct
14 Correct 11 ms 20712 KB Output is correct
15 Correct 14 ms 20692 KB Output is correct
16 Correct 14 ms 20748 KB Output is correct
17 Correct 13 ms 20692 KB Output is correct
18 Correct 11 ms 20692 KB Output is correct
19 Correct 11 ms 20640 KB Output is correct
20 Correct 12 ms 20640 KB Output is correct
21 Correct 12 ms 20692 KB Output is correct
22 Correct 13 ms 20692 KB Output is correct
23 Correct 11 ms 20736 KB Output is correct
24 Correct 10 ms 20692 KB Output is correct
25 Correct 13 ms 20712 KB Output is correct
26 Correct 11 ms 20628 KB Output is correct
27 Correct 13 ms 20744 KB Output is correct
28 Correct 11 ms 20676 KB Output is correct
29 Correct 14 ms 20632 KB Output is correct
30 Correct 438 ms 51788 KB Output is correct
31 Correct 660 ms 48816 KB Output is correct
32 Correct 512 ms 61384 KB Output is correct
33 Correct 493 ms 50412 KB Output is correct
34 Correct 603 ms 49708 KB Output is correct
35 Correct 525 ms 49632 KB Output is correct
36 Correct 467 ms 49444 KB Output is correct
37 Correct 463 ms 71304 KB Output is correct
38 Correct 516 ms 66124 KB Output is correct
39 Correct 371 ms 51660 KB Output is correct
40 Correct 632 ms 48712 KB Output is correct
41 Correct 346 ms 48516 KB Output is correct
42 Correct 405 ms 49212 KB Output is correct
43 Correct 426 ms 48716 KB Output is correct
44 Correct 437 ms 48784 KB Output is correct
45 Correct 550 ms 48828 KB Output is correct
46 Correct 14 ms 20708 KB Output is correct
47 Correct 13 ms 20708 KB Output is correct
48 Correct 11 ms 20740 KB Output is correct
49 Correct 14 ms 20692 KB Output is correct
50 Correct 11 ms 20692 KB Output is correct
51 Correct 12 ms 20692 KB Output is correct
52 Correct 432 ms 51684 KB Output is correct
53 Correct 809 ms 48784 KB Output is correct
54 Correct 520 ms 68608 KB Output is correct
55 Correct 552 ms 50280 KB Output is correct
56 Correct 616 ms 49816 KB Output is correct
57 Correct 591 ms 50120 KB Output is correct
58 Correct 390 ms 49408 KB Output is correct
59 Correct 434 ms 63800 KB Output is correct
60 Correct 605 ms 66172 KB Output is correct
61 Correct 452 ms 52152 KB Output is correct
62 Correct 793 ms 48560 KB Output is correct
63 Correct 11 ms 20692 KB Output is correct
64 Correct 12 ms 20692 KB Output is correct
65 Correct 11 ms 20692 KB Output is correct
66 Correct 11 ms 20792 KB Output is correct
67 Correct 11 ms 20692 KB Output is correct
68 Correct 14 ms 20732 KB Output is correct
69 Correct 12 ms 20696 KB Output is correct
70 Correct 11 ms 20692 KB Output is correct
71 Correct 11 ms 20692 KB Output is correct
72 Correct 13 ms 20692 KB Output is correct
73 Correct 11 ms 20692 KB Output is correct
74 Correct 11 ms 20692 KB Output is correct
75 Correct 11 ms 20732 KB Output is correct
76 Correct 12 ms 20736 KB Output is correct
77 Correct 11 ms 20676 KB Output is correct
78 Correct 11 ms 20692 KB Output is correct
79 Correct 547 ms 68128 KB Output is correct
80 Correct 1793 ms 61560 KB Output is correct
81 Correct 869 ms 63020 KB Output is correct
82 Correct 2212 ms 48664 KB Output is correct
83 Correct 1672 ms 48216 KB Output is correct
84 Correct 1042 ms 48824 KB Output is correct
85 Correct 330 ms 47916 KB Output is correct
86 Correct 555 ms 61256 KB Output is correct
87 Correct 1660 ms 65408 KB Output is correct
88 Correct 1053 ms 49260 KB Output is correct
89 Execution timed out 4091 ms 48288 KB Time limit exceeded
90 Halted 0 ms 0 KB -