oj.uz

Submission #615369

# Submission time Handle Problem Language Result Execution time Memory
615369 2022-07-31T08:38:22 Z 장태환(#8493) Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 89408 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define int long long
int N, L;
struct st
{
	vector<int>r;
	vector<int>lazy;
	int treeN;
	void init(int cnt)
	{
		for (treeN = 1; treeN < cnt; treeN *= 2);
		r.resize(2 * treeN + 3, 1);
		lazy.resize(2 * treeN + 3, 1);
	}
	void ul(int n)
	{
		if (lazy[n] == 1)
			return;
		if (n < treeN)
		{
			lazy[n * 2] *= lazy[n];
			lazy[n * 2] %= L;
			lazy[n * 2+1] *= lazy[n];
			lazy[n * 2+1] %= L;
		}
		else
		{
			r[n] *= lazy[n];
			r[n] %= L;
		}
		lazy[n] = 1;
	}
	void upd(int qs, int qe,int n, int s, int e, int i = 1)
	{
		if (s > qe || qs > e)
			return;
		if (qs <= s && e <= qe)
		{
			lazy[i] *= n;
			lazy[i] %= L;
			return;
		}
		upd(qs, qe, n, s, (s + e) / 2, i * 2);
		upd(qs, qe, n, (s + e) / 2 + 1, e, i * 2 + 1);
	}
	int ge(int qs, int qe, int n,int i = 1)
	{
		ul(i);
		if (qs == qe)
		{
			return r[i];
		}
		int m = (qs + qe) / 2;
		if (n > m)
		{
			return ge(m+1,qe, n, i * 2 + 1);
		}
		else
		{
			return ge(qs, m, n, i * 2);
		}
	}
}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)
				{
					arr[j].upd(lp, rp, w, 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(long long int, long long int)':
sprinkler.cpp:82:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for (i = 0; i < li[n].size(); i++)
      |              ~~^~~~~~~~~~~~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:110:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for (j = 0; j < dl[i].size(); j++)
      |               ~~^~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25428 KB Output is correct
2 Correct 14 ms 25428 KB Output is correct
3 Correct 14 ms 25436 KB Output is correct
4 Correct 15 ms 25684 KB Output is correct
5 Correct 15 ms 25684 KB Output is correct
6 Correct 14 ms 25684 KB Output is correct
7 Correct 14 ms 25684 KB Output is correct
8 Correct 14 ms 25592 KB Output is correct
9 Correct 13 ms 25428 KB Output is correct
10 Correct 13 ms 25428 KB Output is correct
11 Correct 14 ms 25444 KB Output is correct
12 Correct 16 ms 25428 KB Output is correct
13 Correct 13 ms 25444 KB Output is correct
14 Correct 13 ms 25396 KB Output is correct
15 Correct 13 ms 25428 KB Output is correct
16 Correct 13 ms 25428 KB Output is correct
17 Correct 13 ms 25428 KB Output is correct
18 Correct 14 ms 25428 KB Output is correct
19 Correct 13 ms 25428 KB Output is correct
20 Correct 14 ms 25428 KB Output is correct
21 Correct 15 ms 25428 KB Output is correct
22 Correct 14 ms 25332 KB Output is correct
23 Correct 17 ms 25428 KB Output is correct
24 Correct 13 ms 25428 KB Output is correct
25 Correct 13 ms 25436 KB Output is correct
26 Correct 13 ms 25440 KB Output is correct
27 Correct 12 ms 25424 KB Output is correct
28 Correct 13 ms 25428 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25404 KB Output is correct
2 Correct 461 ms 78664 KB Output is correct
3 Correct 706 ms 75688 KB Output is correct
4 Correct 578 ms 81604 KB Output is correct
5 Correct 559 ms 77384 KB Output is correct
6 Correct 584 ms 75880 KB Output is correct
7 Correct 563 ms 75472 KB Output is correct
8 Correct 482 ms 74668 KB Output is correct
9 Correct 506 ms 89408 KB Output is correct
10 Correct 518 ms 85492 KB Output is correct
11 Correct 423 ms 78320 KB Output is correct
12 Correct 697 ms 75988 KB Output is correct
13 Correct 428 ms 74512 KB Output is correct
14 Correct 464 ms 75392 KB Output is correct
15 Correct 505 ms 74756 KB Output is correct
16 Correct 540 ms 74732 KB Output is correct
17 Correct 573 ms 74160 KB Output is correct
18 Correct 14 ms 25428 KB Output is correct
19 Correct 15 ms 25320 KB Output is correct
20 Correct 17 ms 25432 KB Output is correct
21 Correct 16 ms 25348 KB Output is correct
22 Correct 14 ms 25428 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25404 KB Output is correct
2 Correct 461 ms 78664 KB Output is correct
3 Correct 706 ms 75688 KB Output is correct
4 Correct 578 ms 81604 KB Output is correct
5 Correct 559 ms 77384 KB Output is correct
6 Correct 584 ms 75880 KB Output is correct
7 Correct 563 ms 75472 KB Output is correct
8 Correct 482 ms 74668 KB Output is correct
9 Correct 506 ms 89408 KB Output is correct
10 Correct 518 ms 85492 KB Output is correct
11 Correct 423 ms 78320 KB Output is correct
12 Correct 697 ms 75988 KB Output is correct
13 Correct 428 ms 74512 KB Output is correct
14 Correct 464 ms 75392 KB Output is correct
15 Correct 505 ms 74756 KB Output is correct
16 Correct 540 ms 74732 KB Output is correct
17 Correct 573 ms 74160 KB Output is correct
18 Correct 14 ms 25428 KB Output is correct
19 Correct 15 ms 25320 KB Output is correct
20 Correct 17 ms 25432 KB Output is correct
21 Correct 16 ms 25348 KB Output is correct
22 Correct 14 ms 25428 KB Output is correct
23 Correct 13 ms 25432 KB Output is correct
24 Correct 445 ms 78240 KB Output is correct
25 Correct 910 ms 75620 KB Output is correct
26 Correct 554 ms 87040 KB Output is correct
27 Correct 567 ms 77016 KB Output is correct
28 Correct 662 ms 76200 KB Output is correct
29 Correct 650 ms 76940 KB Output is correct
30 Correct 430 ms 74756 KB Output is correct
31 Correct 496 ms 85864 KB Output is correct
32 Correct 610 ms 84860 KB Output is correct
33 Correct 433 ms 78796 KB Output is correct
34 Correct 861 ms 75024 KB Output is correct
35 Correct 15 ms 25428 KB Output is correct
36 Correct 15 ms 25428 KB Output is correct
37 Correct 13 ms 25352 KB Output is correct
38 Correct 17 ms 25428 KB Output is correct
39 Correct 18 ms 25452 KB Output is correct
40 Correct 13 ms 25428 KB Output is correct
41 Correct 14 ms 25428 KB Output is correct
42 Correct 13 ms 25328 KB Output is correct
43 Correct 13 ms 25428 KB Output is correct
44 Correct 13 ms 25408 KB Output is correct
45 Correct 13 ms 25420 KB Output is correct
46 Correct 13 ms 25332 KB Output is correct
47 Correct 13 ms 25448 KB Output is correct
48 Correct 13 ms 25440 KB Output is correct
49 Correct 14 ms 25448 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25428 KB Output is correct
2 Correct 708 ms 86728 KB Output is correct
3 Correct 2713 ms 83132 KB Output is correct
4 Correct 1343 ms 82520 KB Output is correct
5 Correct 2719 ms 75368 KB Output is correct
6 Correct 1789 ms 74532 KB Output is correct
7 Correct 1088 ms 75440 KB Output is correct
8 Correct 346 ms 73132 KB Output is correct
9 Correct 833 ms 81316 KB Output is correct
10 Correct 3122 ms 85084 KB Output is correct
11 Correct 1380 ms 76324 KB Output is correct
12 Execution timed out 4075 ms 74932 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 25348 KB Output is correct
2 Correct 949 ms 85336 KB Output is correct
3 Correct 3156 ms 80548 KB Output is correct
4 Correct 1277 ms 80928 KB Output is correct
5 Correct 2627 ms 77244 KB Output is correct
6 Correct 1717 ms 76440 KB Output is correct
7 Correct 1173 ms 74700 KB Output is correct
8 Correct 363 ms 74436 KB Output is correct
9 Correct 816 ms 88648 KB Output is correct
10 Correct 2377 ms 85120 KB Output is correct
11 Correct 1386 ms 78244 KB Output is correct
12 Execution timed out 4096 ms 75384 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25428 KB Output is correct
2 Correct 14 ms 25428 KB Output is correct
3 Correct 14 ms 25436 KB Output is correct
4 Correct 15 ms 25684 KB Output is correct
5 Correct 15 ms 25684 KB Output is correct
6 Correct 14 ms 25684 KB Output is correct
7 Correct 14 ms 25684 KB Output is correct
8 Correct 14 ms 25592 KB Output is correct
9 Correct 13 ms 25428 KB Output is correct
10 Correct 13 ms 25428 KB Output is correct
11 Correct 14 ms 25444 KB Output is correct
12 Correct 16 ms 25428 KB Output is correct
13 Correct 13 ms 25444 KB Output is correct
14 Correct 13 ms 25396 KB Output is correct
15 Correct 13 ms 25428 KB Output is correct
16 Correct 13 ms 25428 KB Output is correct
17 Correct 13 ms 25428 KB Output is correct
18 Correct 14 ms 25428 KB Output is correct
19 Correct 13 ms 25428 KB Output is correct
20 Correct 14 ms 25428 KB Output is correct
21 Correct 15 ms 25428 KB Output is correct
22 Correct 14 ms 25332 KB Output is correct
23 Correct 17 ms 25428 KB Output is correct
24 Correct 13 ms 25428 KB Output is correct
25 Correct 13 ms 25436 KB Output is correct
26 Correct 13 ms 25440 KB Output is correct
27 Correct 12 ms 25424 KB Output is correct
28 Correct 13 ms 25428 KB Output is correct
29 Correct 13 ms 25404 KB Output is correct
30 Correct 461 ms 78664 KB Output is correct
31 Correct 706 ms 75688 KB Output is correct
32 Correct 578 ms 81604 KB Output is correct
33 Correct 559 ms 77384 KB Output is correct
34 Correct 584 ms 75880 KB Output is correct
35 Correct 563 ms 75472 KB Output is correct
36 Correct 482 ms 74668 KB Output is correct
37 Correct 506 ms 89408 KB Output is correct
38 Correct 518 ms 85492 KB Output is correct
39 Correct 423 ms 78320 KB Output is correct
40 Correct 697 ms 75988 KB Output is correct
41 Correct 428 ms 74512 KB Output is correct
42 Correct 464 ms 75392 KB Output is correct
43 Correct 505 ms 74756 KB Output is correct
44 Correct 540 ms 74732 KB Output is correct
45 Correct 573 ms 74160 KB Output is correct
46 Correct 14 ms 25428 KB Output is correct
47 Correct 15 ms 25320 KB Output is correct
48 Correct 17 ms 25432 KB Output is correct
49 Correct 16 ms 25348 KB Output is correct
50 Correct 14 ms 25428 KB Output is correct
51 Correct 13 ms 25432 KB Output is correct
52 Correct 445 ms 78240 KB Output is correct
53 Correct 910 ms 75620 KB Output is correct
54 Correct 554 ms 87040 KB Output is correct
55 Correct 567 ms 77016 KB Output is correct
56 Correct 662 ms 76200 KB Output is correct
57 Correct 650 ms 76940 KB Output is correct
58 Correct 430 ms 74756 KB Output is correct
59 Correct 496 ms 85864 KB Output is correct
60 Correct 610 ms 84860 KB Output is correct
61 Correct 433 ms 78796 KB Output is correct
62 Correct 861 ms 75024 KB Output is correct
63 Correct 15 ms 25428 KB Output is correct
64 Correct 15 ms 25428 KB Output is correct
65 Correct 13 ms 25352 KB Output is correct
66 Correct 17 ms 25428 KB Output is correct
67 Correct 18 ms 25452 KB Output is correct
68 Correct 13 ms 25428 KB Output is correct
69 Correct 14 ms 25428 KB Output is correct
70 Correct 13 ms 25328 KB Output is correct
71 Correct 13 ms 25428 KB Output is correct
72 Correct 13 ms 25408 KB Output is correct
73 Correct 13 ms 25420 KB Output is correct
74 Correct 13 ms 25332 KB Output is correct
75 Correct 13 ms 25448 KB Output is correct
76 Correct 13 ms 25440 KB Output is correct
77 Correct 14 ms 25448 KB Output is correct
78 Correct 14 ms 25428 KB Output is correct
79 Correct 708 ms 86728 KB Output is correct
80 Correct 2713 ms 83132 KB Output is correct
81 Correct 1343 ms 82520 KB Output is correct
82 Correct 2719 ms 75368 KB Output is correct
83 Correct 1789 ms 74532 KB Output is correct
84 Correct 1088 ms 75440 KB Output is correct
85 Correct 346 ms 73132 KB Output is correct
86 Correct 833 ms 81316 KB Output is correct
87 Correct 3122 ms 85084 KB Output is correct
88 Correct 1380 ms 76324 KB Output is correct
89 Execution timed out 4075 ms 74932 KB Time limit exceeded
90 Halted 0 ms 0 KB -