oj.uz

Submission #893054

# Submission time Handle Problem Language Result Execution time Memory
893054 2023-12-26T12:22:56 Z smartmonky Sprinkler (JOI22_sprinkler) C++14
100 / 100
 924 ms 108360 KB 
#include <bits/stdc++.h>
 
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define rnd(l, r) uniform_int_distribution<int>(l, r)(rng)
 
using namespace std;

void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);} 
int pow(int a,int b,int m){int ans=1;while(b){if(b&1){ans=(ans*a)%m;}b>>=1;a=(a*a)%m;}return ans;}
int binpow(int a,int b){int ans=1;while(b){if(b&1){ans=(ans*a);}b>>=1;a=(a*a);}return ans;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 10, inf = 1e9;

vector <int> g[N];
int cost[N];
 
int h[N][50];
int par[N];

void dfs(int v, int p){
	par[v] = p;
	for(auto to : g[v]){
		if(to == p)continue;
		dfs(to, v);
	}
}

main(){
	iostream::sync_with_stdio(false);	
    cin.tie(nullptr);
    cout.tie(nullptr);
	int n, l;
	cin >> n >> l;
	for(int i = 0; i < n - 1; i ++){
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	for(int i = 1; i <= n; i++){
		cin >> cost[i];
		for(int j = 0; j <= 45; j++){
			h[i][j] = 1;
		}
	}
	
	int q;
	cin >> q;
		dfs(1, 1);
		while(q--){
			int tp;
			cin >> tp;
			if(tp == 1){
				int x, d, w;
				cin >> x >> d >> w;
				while(d > 0 && par[x] != x){
					h[x][d] =( h[x][d] * w) % l;
					h[x][d - 1] = (h[x][d - 1] * w) % l;
					x = par[x];
					d--;
				}
				while(d > 0){
					h[x][d] = (h[x][d] * w) % l;
					d--;
				}
				h[x][0] = (h[x][0] * w) % l;
			}else{
				int x;
				cin >> x;
				int res = cost[x];
				for(int i = 0; i <= 40; i++){
					res *= h[x][i];
					res %= l;
					if(x == par[x])break;
					x = par[x];
				}
				cout << res % l<< endl;
			}
		}
}
/*
 * Before implementing the problem:
	
	Do I understand the problem correctly?
	Which places are tricky? What do I need to remember to implement them correctly?
	Which place is the heaviest by implementation? Can I do it simpler?
	Which place is the slowest? Where do I need to be careful about constant factors and where I can choose slower but simpler implementation?
	----------------------------------
	If not AC:
 
	Did you remember to do everything to handle the tricky places you thought about before?
	Is the solution correct?
	Do I understand the problem correctly?
	----------------------------------
	If you have a test on which the solution gives wrong answer:
 
	Is the solution doing what it was supposed to do?
	Is the problem in the code or in the idea?
*/

Compilation message

sprinkler.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      | ^~~~
sprinkler.cpp: In function 'void fp(std::string)':
sprinkler.cpp:13:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:13:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | void fp(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 3 ms 10332 KB Output is correct
5 Correct 3 ms 10332 KB Output is correct
6 Correct 4 ms 10332 KB Output is correct
7 Correct 3 ms 10332 KB Output is correct
8 Correct 3 ms 10332 KB Output is correct
9 Correct 3 ms 10332 KB Output is correct
10 Correct 3 ms 10420 KB Output is correct
11 Correct 3 ms 10328 KB Output is correct
12 Correct 3 ms 10332 KB Output is correct
13 Correct 3 ms 10332 KB Output is correct
14 Correct 3 ms 10332 KB Output is correct
15 Correct 3 ms 10332 KB Output is correct
16 Correct 3 ms 10572 KB Output is correct
17 Correct 3 ms 10328 KB Output is correct
18 Correct 3 ms 10328 KB Output is correct
19 Correct 3 ms 10332 KB Output is correct
20 Correct 3 ms 10332 KB Output is correct
21 Correct 3 ms 10476 KB Output is correct
22 Correct 3 ms 10332 KB Output is correct
23 Correct 3 ms 10332 KB Output is correct
24 Correct 3 ms 10332 KB Output is correct
25 Correct 3 ms 10332 KB Output is correct
26 Correct 3 ms 10328 KB Output is correct
27 Correct 3 ms 10328 KB Output is correct
28 Correct 3 ms 10332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 760 ms 103880 KB Output is correct
3 Correct 303 ms 103508 KB Output is correct
4 Correct 580 ms 106120 KB Output is correct
5 Correct 528 ms 103744 KB Output is correct
6 Correct 461 ms 103456 KB Output is correct
7 Correct 463 ms 103964 KB Output is correct
8 Correct 412 ms 104128 KB Output is correct
9 Correct 841 ms 108360 KB Output is correct
10 Correct 337 ms 107404 KB Output is correct
11 Correct 752 ms 104404 KB Output is correct
12 Correct 306 ms 103252 KB Output is correct
13 Correct 227 ms 104096 KB Output is correct
14 Correct 224 ms 103868 KB Output is correct
15 Correct 224 ms 103352 KB Output is correct
16 Correct 233 ms 103768 KB Output is correct
17 Correct 229 ms 104212 KB Output is correct
18 Correct 3 ms 10332 KB Output is correct
19 Correct 3 ms 10332 KB Output is correct
20 Correct 3 ms 10332 KB Output is correct
21 Correct 3 ms 10332 KB Output is correct
22 Correct 3 ms 10332 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 760 ms 103880 KB Output is correct
3 Correct 303 ms 103508 KB Output is correct
4 Correct 580 ms 106120 KB Output is correct
5 Correct 528 ms 103744 KB Output is correct
6 Correct 461 ms 103456 KB Output is correct
7 Correct 463 ms 103964 KB Output is correct
8 Correct 412 ms 104128 KB Output is correct
9 Correct 841 ms 108360 KB Output is correct
10 Correct 337 ms 107404 KB Output is correct
11 Correct 752 ms 104404 KB Output is correct
12 Correct 306 ms 103252 KB Output is correct
13 Correct 227 ms 104096 KB Output is correct
14 Correct 224 ms 103868 KB Output is correct
15 Correct 224 ms 103352 KB Output is correct
16 Correct 233 ms 103768 KB Output is correct
17 Correct 229 ms 104212 KB Output is correct
18 Correct 3 ms 10332 KB Output is correct
19 Correct 3 ms 10332 KB Output is correct
20 Correct 3 ms 10332 KB Output is correct
21 Correct 3 ms 10332 KB Output is correct
22 Correct 3 ms 10332 KB Output is correct
23 Correct 2 ms 10332 KB Output is correct
24 Correct 751 ms 104108 KB Output is correct
25 Correct 311 ms 103248 KB Output is correct
26 Correct 578 ms 108152 KB Output is correct
27 Correct 564 ms 103712 KB Output is correct
28 Correct 455 ms 103928 KB Output is correct
29 Correct 473 ms 103640 KB Output is correct
30 Correct 413 ms 104188 KB Output is correct
31 Correct 848 ms 106740 KB Output is correct
32 Correct 323 ms 107264 KB Output is correct
33 Correct 742 ms 104272 KB Output is correct
34 Correct 312 ms 103252 KB Output is correct
35 Correct 3 ms 10328 KB Output is correct
36 Correct 3 ms 10332 KB Output is correct
37 Correct 3 ms 10332 KB Output is correct
38 Correct 3 ms 10356 KB Output is correct
39 Correct 3 ms 10484 KB Output is correct
40 Correct 3 ms 10332 KB Output is correct
41 Correct 3 ms 10332 KB Output is correct
42 Correct 3 ms 10332 KB Output is correct
43 Correct 3 ms 10372 KB Output is correct
44 Correct 3 ms 10332 KB Output is correct
45 Correct 3 ms 10332 KB Output is correct
46 Correct 3 ms 10332 KB Output is correct
47 Correct 3 ms 10332 KB Output is correct
48 Correct 3 ms 10332 KB Output is correct
49 Correct 3 ms 10332 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10332 KB Output is correct
2 Correct 852 ms 105248 KB Output is correct
3 Correct 599 ms 101912 KB Output is correct
4 Correct 658 ms 102228 KB Output is correct
5 Correct 590 ms 99204 KB Output is correct
6 Correct 486 ms 98972 KB Output is correct
7 Correct 474 ms 99296 KB Output is correct
8 Correct 418 ms 99688 KB Output is correct
9 Correct 857 ms 101600 KB Output is correct
10 Correct 649 ms 102856 KB Output is correct
11 Correct 748 ms 98944 KB Output is correct
12 Correct 491 ms 98900 KB Output is correct
13 Correct 343 ms 99848 KB Output is correct
14 Correct 351 ms 100728 KB Output is correct
15 Correct 3 ms 10328 KB Output is correct
16 Correct 3 ms 10332 KB Output is correct
17 Correct 3 ms 10332 KB Output is correct
18 Correct 3 ms 10332 KB Output is correct
19 Correct 3 ms 10332 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 905 ms 104296 KB Output is correct
3 Correct 627 ms 100940 KB Output is correct
4 Correct 671 ms 102552 KB Output is correct
5 Correct 571 ms 100312 KB Output is correct
6 Correct 488 ms 100432 KB Output is correct
7 Correct 480 ms 100492 KB Output is correct
8 Correct 410 ms 100364 KB Output is correct
9 Correct 877 ms 105272 KB Output is correct
10 Correct 741 ms 103064 KB Output is correct
11 Correct 892 ms 101432 KB Output is correct
12 Correct 550 ms 99256 KB Output is correct
13 Correct 375 ms 100496 KB Output is correct
14 Correct 379 ms 100752 KB Output is correct
15 Correct 3 ms 10332 KB Output is correct
16 Correct 3 ms 10332 KB Output is correct
17 Correct 3 ms 10472 KB Output is correct
18 Correct 3 ms 10472 KB Output is correct
19 Correct 3 ms 10492 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10332 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 3 ms 10332 KB Output is correct
5 Correct 3 ms 10332 KB Output is correct
6 Correct 4 ms 10332 KB Output is correct
7 Correct 3 ms 10332 KB Output is correct
8 Correct 3 ms 10332 KB Output is correct
9 Correct 3 ms 10332 KB Output is correct
10 Correct 3 ms 10420 KB Output is correct
11 Correct 3 ms 10328 KB Output is correct
12 Correct 3 ms 10332 KB Output is correct
13 Correct 3 ms 10332 KB Output is correct
14 Correct 3 ms 10332 KB Output is correct
15 Correct 3 ms 10332 KB Output is correct
16 Correct 3 ms 10572 KB Output is correct
17 Correct 3 ms 10328 KB Output is correct
18 Correct 3 ms 10328 KB Output is correct
19 Correct 3 ms 10332 KB Output is correct
20 Correct 3 ms 10332 KB Output is correct
21 Correct 3 ms 10476 KB Output is correct
22 Correct 3 ms 10332 KB Output is correct
23 Correct 3 ms 10332 KB Output is correct
24 Correct 3 ms 10332 KB Output is correct
25 Correct 3 ms 10332 KB Output is correct
26 Correct 3 ms 10328 KB Output is correct
27 Correct 3 ms 10328 KB Output is correct
28 Correct 3 ms 10332 KB Output is correct
29 Correct 2 ms 10332 KB Output is correct
30 Correct 760 ms 103880 KB Output is correct
31 Correct 303 ms 103508 KB Output is correct
32 Correct 580 ms 106120 KB Output is correct
33 Correct 528 ms 103744 KB Output is correct
34 Correct 461 ms 103456 KB Output is correct
35 Correct 463 ms 103964 KB Output is correct
36 Correct 412 ms 104128 KB Output is correct
37 Correct 841 ms 108360 KB Output is correct
38 Correct 337 ms 107404 KB Output is correct
39 Correct 752 ms 104404 KB Output is correct
40 Correct 306 ms 103252 KB Output is correct
41 Correct 227 ms 104096 KB Output is correct
42 Correct 224 ms 103868 KB Output is correct
43 Correct 224 ms 103352 KB Output is correct
44 Correct 233 ms 103768 KB Output is correct
45 Correct 229 ms 104212 KB Output is correct
46 Correct 3 ms 10332 KB Output is correct
47 Correct 3 ms 10332 KB Output is correct
48 Correct 3 ms 10332 KB Output is correct
49 Correct 3 ms 10332 KB Output is correct
50 Correct 3 ms 10332 KB Output is correct
51 Correct 2 ms 10332 KB Output is correct
52 Correct 751 ms 104108 KB Output is correct
53 Correct 311 ms 103248 KB Output is correct
54 Correct 578 ms 108152 KB Output is correct
55 Correct 564 ms 103712 KB Output is correct
56 Correct 455 ms 103928 KB Output is correct
57 Correct 473 ms 103640 KB Output is correct
58 Correct 413 ms 104188 KB Output is correct
59 Correct 848 ms 106740 KB Output is correct
60 Correct 323 ms 107264 KB Output is correct
61 Correct 742 ms 104272 KB Output is correct
62 Correct 312 ms 103252 KB Output is correct
63 Correct 3 ms 10328 KB Output is correct
64 Correct 3 ms 10332 KB Output is correct
65 Correct 3 ms 10332 KB Output is correct
66 Correct 3 ms 10356 KB Output is correct
67 Correct 3 ms 10484 KB Output is correct
68 Correct 3 ms 10332 KB Output is correct
69 Correct 3 ms 10332 KB Output is correct
70 Correct 3 ms 10332 KB Output is correct
71 Correct 3 ms 10372 KB Output is correct
72 Correct 3 ms 10332 KB Output is correct
73 Correct 3 ms 10332 KB Output is correct
74 Correct 3 ms 10332 KB Output is correct
75 Correct 3 ms 10332 KB Output is correct
76 Correct 3 ms 10332 KB Output is correct
77 Correct 3 ms 10332 KB Output is correct
78 Correct 3 ms 10332 KB Output is correct
79 Correct 852 ms 105248 KB Output is correct
80 Correct 599 ms 101912 KB Output is correct
81 Correct 658 ms 102228 KB Output is correct
82 Correct 590 ms 99204 KB Output is correct
83 Correct 486 ms 98972 KB Output is correct
84 Correct 474 ms 99296 KB Output is correct
85 Correct 418 ms 99688 KB Output is correct
86 Correct 857 ms 101600 KB Output is correct
87 Correct 649 ms 102856 KB Output is correct
88 Correct 748 ms 98944 KB Output is correct
89 Correct 491 ms 98900 KB Output is correct
90 Correct 343 ms 99848 KB Output is correct
91 Correct 351 ms 100728 KB Output is correct
92 Correct 3 ms 10328 KB Output is correct
93 Correct 3 ms 10332 KB Output is correct
94 Correct 3 ms 10332 KB Output is correct
95 Correct 3 ms 10332 KB Output is correct
96 Correct 3 ms 10332 KB Output is correct
97 Correct 2 ms 10584 KB Output is correct
98 Correct 905 ms 104296 KB Output is correct
99 Correct 627 ms 100940 KB Output is correct
100 Correct 671 ms 102552 KB Output is correct
101 Correct 571 ms 100312 KB Output is correct
102 Correct 488 ms 100432 KB Output is correct
103 Correct 480 ms 100492 KB Output is correct
104 Correct 410 ms 100364 KB Output is correct
105 Correct 877 ms 105272 KB Output is correct
106 Correct 741 ms 103064 KB Output is correct
107 Correct 892 ms 101432 KB Output is correct
108 Correct 550 ms 99256 KB Output is correct
109 Correct 375 ms 100496 KB Output is correct
110 Correct 379 ms 100752 KB Output is correct
111 Correct 3 ms 10332 KB Output is correct
112 Correct 3 ms 10332 KB Output is correct
113 Correct 3 ms 10472 KB Output is correct
114 Correct 3 ms 10472 KB Output is correct
115 Correct 3 ms 10492 KB Output is correct
116 Correct 883 ms 99632 KB Output is correct
117 Correct 598 ms 100368 KB Output is correct
118 Correct 762 ms 105104 KB Output is correct
119 Correct 648 ms 100940 KB Output is correct
120 Correct 588 ms 100696 KB Output is correct
121 Correct 560 ms 101532 KB Output is correct
122 Correct 459 ms 101568 KB Output is correct
123 Correct 924 ms 104852 KB Output is correct
124 Correct 661 ms 102452 KB Output is correct
125 Correct 812 ms 101140 KB Output is correct
126 Correct 547 ms 100280 KB Output is correct
127 Correct 536 ms 100560 KB Output is correct
128 Correct 452 ms 101156 KB Output is correct
129 Correct 463 ms 102224 KB Output is correct