oj.uz

Submission #615432

# Submission time Handle Problem Language Result Execution time Memory
615432 2022-07-31T09:09:59 Z 장태환(#8493) Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 72060 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;
			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(), 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:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (i = 0; i < li[n].size(); i++)
      |              ~~^~~~~~~~~~~~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:92: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]
   92 |   for (j = 0; j < dl[i].size(); j++)
      |               ~~^~~~~~~~~~~~~~
sprinkler.cpp:125:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     if (lp!=dl2[j].size()&&dl2[j][lp]<=en[cp])
      |         ~~^~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20692 KB Output is correct
2 Correct 10 ms 20692 KB Output is correct
3 Correct 11 ms 20708 KB Output is correct
4 Correct 15 ms 20888 KB Output is correct
5 Correct 12 ms 20820 KB Output is correct
6 Correct 11 ms 20820 KB Output is correct
7 Correct 15 ms 20772 KB Output is correct
8 Correct 14 ms 20884 KB Output is correct
9 Correct 14 ms 20692 KB Output is correct
10 Correct 12 ms 20736 KB Output is correct
11 Correct 12 ms 20648 KB Output is correct
12 Correct 14 ms 20692 KB Output is correct
13 Correct 11 ms 20672 KB Output is correct
14 Correct 10 ms 20692 KB Output is correct
15 Correct 10 ms 20744 KB Output is correct
16 Correct 11 ms 20744 KB Output is correct
17 Correct 11 ms 20692 KB Output is correct
18 Correct 11 ms 20692 KB Output is correct
19 Correct 11 ms 20632 KB Output is correct
20 Correct 11 ms 20680 KB Output is correct
21 Correct 11 ms 20724 KB Output is correct
22 Correct 10 ms 20740 KB Output is correct
23 Correct 11 ms 20740 KB Output is correct
24 Correct 13 ms 20640 KB Output is correct
25 Correct 11 ms 20692 KB Output is correct
26 Correct 13 ms 20692 KB Output is correct
27 Correct 11 ms 20692 KB Output is correct
28 Correct 10 ms 20748 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20692 KB Output is correct
2 Correct 438 ms 51852 KB Output is correct
3 Correct 654 ms 48896 KB Output is correct
4 Correct 464 ms 61380 KB Output is correct
5 Correct 584 ms 50460 KB Output is correct
6 Correct 558 ms 49712 KB Output is correct
7 Correct 577 ms 49548 KB Output is correct
8 Correct 470 ms 49428 KB Output is correct
9 Correct 555 ms 71248 KB Output is correct
10 Correct 539 ms 66104 KB Output is correct
11 Correct 421 ms 51668 KB Output is correct
12 Correct 574 ms 48720 KB Output is correct
13 Correct 365 ms 48552 KB Output is correct
14 Correct 410 ms 48948 KB Output is correct
15 Correct 429 ms 48716 KB Output is correct
16 Correct 446 ms 48764 KB Output is correct
17 Correct 555 ms 48756 KB Output is correct
18 Correct 11 ms 20692 KB Output is correct
19 Correct 13 ms 20708 KB Output is correct
20 Correct 11 ms 20712 KB Output is correct
21 Correct 11 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 11 ms 20692 KB Output is correct
2 Correct 438 ms 51852 KB Output is correct
3 Correct 654 ms 48896 KB Output is correct
4 Correct 464 ms 61380 KB Output is correct
5 Correct 584 ms 50460 KB Output is correct
6 Correct 558 ms 49712 KB Output is correct
7 Correct 577 ms 49548 KB Output is correct
8 Correct 470 ms 49428 KB Output is correct
9 Correct 555 ms 71248 KB Output is correct
10 Correct 539 ms 66104 KB Output is correct
11 Correct 421 ms 51668 KB Output is correct
12 Correct 574 ms 48720 KB Output is correct
13 Correct 365 ms 48552 KB Output is correct
14 Correct 410 ms 48948 KB Output is correct
15 Correct 429 ms 48716 KB Output is correct
16 Correct 446 ms 48764 KB Output is correct
17 Correct 555 ms 48756 KB Output is correct
18 Correct 11 ms 20692 KB Output is correct
19 Correct 13 ms 20708 KB Output is correct
20 Correct 11 ms 20712 KB Output is correct
21 Correct 11 ms 20692 KB Output is correct
22 Correct 11 ms 20692 KB Output is correct
23 Correct 12 ms 20724 KB Output is correct
24 Correct 411 ms 51820 KB Output is correct
25 Correct 722 ms 48776 KB Output is correct
26 Correct 508 ms 68532 KB Output is correct
27 Correct 527 ms 50172 KB Output is correct
28 Correct 615 ms 49828 KB Output is correct
29 Correct 597 ms 50160 KB Output is correct
30 Correct 373 ms 49492 KB Output is correct
31 Correct 430 ms 63748 KB Output is correct
32 Correct 597 ms 66176 KB Output is correct
33 Correct 416 ms 51940 KB Output is correct
34 Correct 775 ms 48544 KB Output is correct
35 Correct 11 ms 20692 KB Output is correct
36 Correct 11 ms 20692 KB Output is correct
37 Correct 11 ms 20692 KB Output is correct
38 Correct 12 ms 20740 KB Output is correct
39 Correct 11 ms 20740 KB Output is correct
40 Correct 11 ms 20692 KB Output is correct
41 Correct 13 ms 20632 KB Output is correct
42 Correct 11 ms 20732 KB Output is correct
43 Correct 11 ms 20644 KB Output is correct
44 Correct 11 ms 20692 KB Output is correct
45 Correct 12 ms 20748 KB Output is correct
46 Correct 12 ms 20700 KB Output is correct
47 Correct 11 ms 20636 KB Output is correct
48 Correct 11 ms 20692 KB Output is correct
49 Correct 13 ms 20692 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 563 ms 68172 KB Output is correct
3 Correct 1742 ms 61520 KB Output is correct
4 Correct 878 ms 63216 KB Output is correct
5 Correct 2106 ms 48572 KB Output is correct
6 Correct 1569 ms 48284 KB Output is correct
7 Correct 963 ms 48660 KB Output is correct
8 Correct 338 ms 47800 KB Output is correct
9 Correct 563 ms 61300 KB Output is correct
10 Correct 1586 ms 65360 KB Output is correct
11 Correct 1090 ms 49184 KB Output is correct
12 Execution timed out 4094 ms 48264 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20628 KB Output is correct
2 Correct 746 ms 66116 KB Output is correct
3 Correct 2449 ms 61028 KB Output is correct
4 Correct 1058 ms 63432 KB Output is correct
5 Correct 2611 ms 53800 KB Output is correct
6 Correct 2168 ms 52480 KB Output is correct
7 Correct 1476 ms 51752 KB Output is correct
8 Correct 370 ms 51920 KB Output is correct
9 Correct 777 ms 72060 KB Output is correct
10 Correct 2064 ms 69172 KB Output is correct
11 Correct 1484 ms 54232 KB Output is correct
12 Execution timed out 4054 ms 50604 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20692 KB Output is correct
2 Correct 10 ms 20692 KB Output is correct
3 Correct 11 ms 20708 KB Output is correct
4 Correct 15 ms 20888 KB Output is correct
5 Correct 12 ms 20820 KB Output is correct
6 Correct 11 ms 20820 KB Output is correct
7 Correct 15 ms 20772 KB Output is correct
8 Correct 14 ms 20884 KB Output is correct
9 Correct 14 ms 20692 KB Output is correct
10 Correct 12 ms 20736 KB Output is correct
11 Correct 12 ms 20648 KB Output is correct
12 Correct 14 ms 20692 KB Output is correct
13 Correct 11 ms 20672 KB Output is correct
14 Correct 10 ms 20692 KB Output is correct
15 Correct 10 ms 20744 KB Output is correct
16 Correct 11 ms 20744 KB Output is correct
17 Correct 11 ms 20692 KB Output is correct
18 Correct 11 ms 20692 KB Output is correct
19 Correct 11 ms 20632 KB Output is correct
20 Correct 11 ms 20680 KB Output is correct
21 Correct 11 ms 20724 KB Output is correct
22 Correct 10 ms 20740 KB Output is correct
23 Correct 11 ms 20740 KB Output is correct
24 Correct 13 ms 20640 KB Output is correct
25 Correct 11 ms 20692 KB Output is correct
26 Correct 13 ms 20692 KB Output is correct
27 Correct 11 ms 20692 KB Output is correct
28 Correct 10 ms 20748 KB Output is correct
29 Correct 11 ms 20692 KB Output is correct
30 Correct 438 ms 51852 KB Output is correct
31 Correct 654 ms 48896 KB Output is correct
32 Correct 464 ms 61380 KB Output is correct
33 Correct 584 ms 50460 KB Output is correct
34 Correct 558 ms 49712 KB Output is correct
35 Correct 577 ms 49548 KB Output is correct
36 Correct 470 ms 49428 KB Output is correct
37 Correct 555 ms 71248 KB Output is correct
38 Correct 539 ms 66104 KB Output is correct
39 Correct 421 ms 51668 KB Output is correct
40 Correct 574 ms 48720 KB Output is correct
41 Correct 365 ms 48552 KB Output is correct
42 Correct 410 ms 48948 KB Output is correct
43 Correct 429 ms 48716 KB Output is correct
44 Correct 446 ms 48764 KB Output is correct
45 Correct 555 ms 48756 KB Output is correct
46 Correct 11 ms 20692 KB Output is correct
47 Correct 13 ms 20708 KB Output is correct
48 Correct 11 ms 20712 KB Output is correct
49 Correct 11 ms 20692 KB Output is correct
50 Correct 11 ms 20692 KB Output is correct
51 Correct 12 ms 20724 KB Output is correct
52 Correct 411 ms 51820 KB Output is correct
53 Correct 722 ms 48776 KB Output is correct
54 Correct 508 ms 68532 KB Output is correct
55 Correct 527 ms 50172 KB Output is correct
56 Correct 615 ms 49828 KB Output is correct
57 Correct 597 ms 50160 KB Output is correct
58 Correct 373 ms 49492 KB Output is correct
59 Correct 430 ms 63748 KB Output is correct
60 Correct 597 ms 66176 KB Output is correct
61 Correct 416 ms 51940 KB Output is correct
62 Correct 775 ms 48544 KB Output is correct
63 Correct 11 ms 20692 KB Output is correct
64 Correct 11 ms 20692 KB Output is correct
65 Correct 11 ms 20692 KB Output is correct
66 Correct 12 ms 20740 KB Output is correct
67 Correct 11 ms 20740 KB Output is correct
68 Correct 11 ms 20692 KB Output is correct
69 Correct 13 ms 20632 KB Output is correct
70 Correct 11 ms 20732 KB Output is correct
71 Correct 11 ms 20644 KB Output is correct
72 Correct 11 ms 20692 KB Output is correct
73 Correct 12 ms 20748 KB Output is correct
74 Correct 12 ms 20700 KB Output is correct
75 Correct 11 ms 20636 KB Output is correct
76 Correct 11 ms 20692 KB Output is correct
77 Correct 13 ms 20692 KB Output is correct
78 Correct 11 ms 20692 KB Output is correct
79 Correct 563 ms 68172 KB Output is correct
80 Correct 1742 ms 61520 KB Output is correct
81 Correct 878 ms 63216 KB Output is correct
82 Correct 2106 ms 48572 KB Output is correct
83 Correct 1569 ms 48284 KB Output is correct
84 Correct 963 ms 48660 KB Output is correct
85 Correct 338 ms 47800 KB Output is correct
86 Correct 563 ms 61300 KB Output is correct
87 Correct 1586 ms 65360 KB Output is correct
88 Correct 1090 ms 49184 KB Output is correct
89 Execution timed out 4094 ms 48264 KB Time limit exceeded
90 Halted 0 ms 0 KB -