oj.uz

Submission #590894

# Submission time Handle Problem Language Result Execution time Memory
590894 2022-07-06T13:30:20 Z keta_tsimakuridze Sprinkler (JOI22_sprinkler) C++17
100 / 100
 713 ms 82832 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define endl "\n"
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7; // !
int t, h[N], cn[N][42], p[N];
vector<int> V[N];
void dfs(int u, int P) {
    for(int i = 0; i < V[u].size(); i++) {
        if(V[u][i] != P) p[V[u][i]] = u, dfs(V[u][i], u);
    }
}
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n, L;
    cin >> n >> L;
    for(int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        V[u].push_back(v);
        V[v].push_back(u);
    }
    for(int i = n + 40; i > n; i--) {
        V[i].push_back(i - 1);
    }
    dfs(n + 40, 0);
    for(int i = 1; i <= n + 40; i++) {
        for(int d = 0; d <= 40; d++) cn[i][d] = 1;
    }
    for(int i = 1; i <= n; i++) cin >> h[i];
    int q;
    cin >> q;
    while(q--) {
        cin >> t;
        if(t == 1) {
            int x, d, w;
            cin >> x >> d >> w;
            // d1 + d2 = d,     d1 + (40 - d) + d2 = 40
            d = 40 - d;
            while(d <= 40) {
                cn[x][d] = (ll)cn[x][d] * w % L;
                ++d;
                x = p[x];
            }
            continue;
        }
        int x;
        cin >> x;
        int ans = h[x], d = 0;
        while(x && d <= 40){
            ans = (ll)ans * cn[x][40 - d] % L;
            if(d != 40) ans = (ll)ans * cn[x][39 - d] % L;
            ++d;
            x = p[x];
        }
        cout << ans << endl;
    }
}

Compilation message

sprinkler.cpp: In function 'void dfs(int, int)':
sprinkler.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
sprinkler.cpp: At global scope:
sprinkler.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      | ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 13 ms 24068 KB Output is correct
6 Correct 13 ms 24088 KB Output is correct
7 Correct 12 ms 24072 KB Output is correct
8 Correct 13 ms 24012 KB Output is correct
9 Correct 12 ms 23892 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 13 ms 23752 KB Output is correct
12 Correct 13 ms 23792 KB Output is correct
13 Correct 14 ms 23892 KB Output is correct
14 Correct 13 ms 23744 KB Output is correct
15 Correct 12 ms 23764 KB Output is correct
16 Correct 15 ms 23824 KB Output is correct
17 Correct 13 ms 23840 KB Output is correct
18 Correct 12 ms 23764 KB Output is correct
19 Correct 13 ms 23764 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 12 ms 23824 KB Output is correct
22 Correct 13 ms 23764 KB Output is correct
23 Correct 12 ms 23764 KB Output is correct
24 Correct 13 ms 23752 KB Output is correct
25 Correct 12 ms 23820 KB Output is correct
26 Correct 12 ms 23812 KB Output is correct
27 Correct 14 ms 23820 KB Output is correct
28 Correct 14 ms 23764 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 510 ms 75116 KB Output is correct
3 Correct 364 ms 71668 KB Output is correct
4 Correct 544 ms 78452 KB Output is correct
5 Correct 419 ms 73332 KB Output is correct
6 Correct 403 ms 73440 KB Output is correct
7 Correct 377 ms 73712 KB Output is correct
8 Correct 338 ms 73968 KB Output is correct
9 Correct 713 ms 80208 KB Output is correct
10 Correct 373 ms 77644 KB Output is correct
11 Correct 556 ms 75072 KB Output is correct
12 Correct 343 ms 71756 KB Output is correct
13 Correct 254 ms 72280 KB Output is correct
14 Correct 352 ms 72232 KB Output is correct
15 Correct 280 ms 72216 KB Output is correct
16 Correct 255 ms 72132 KB Output is correct
17 Correct 303 ms 72744 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Correct 12 ms 23764 KB Output is correct
20 Correct 12 ms 23840 KB Output is correct
21 Correct 13 ms 23868 KB Output is correct
22 Correct 14 ms 23828 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 510 ms 75116 KB Output is correct
3 Correct 364 ms 71668 KB Output is correct
4 Correct 544 ms 78452 KB Output is correct
5 Correct 419 ms 73332 KB Output is correct
6 Correct 403 ms 73440 KB Output is correct
7 Correct 377 ms 73712 KB Output is correct
8 Correct 338 ms 73968 KB Output is correct
9 Correct 713 ms 80208 KB Output is correct
10 Correct 373 ms 77644 KB Output is correct
11 Correct 556 ms 75072 KB Output is correct
12 Correct 343 ms 71756 KB Output is correct
13 Correct 254 ms 72280 KB Output is correct
14 Correct 352 ms 72232 KB Output is correct
15 Correct 280 ms 72216 KB Output is correct
16 Correct 255 ms 72132 KB Output is correct
17 Correct 303 ms 72744 KB Output is correct
18 Correct 13 ms 23764 KB Output is correct
19 Correct 12 ms 23764 KB Output is correct
20 Correct 12 ms 23840 KB Output is correct
21 Correct 13 ms 23868 KB Output is correct
22 Correct 14 ms 23828 KB Output is correct
23 Correct 12 ms 23792 KB Output is correct
24 Correct 588 ms 75052 KB Output is correct
25 Correct 364 ms 71624 KB Output is correct
26 Correct 556 ms 81640 KB Output is correct
27 Correct 480 ms 73384 KB Output is correct
28 Correct 416 ms 73464 KB Output is correct
29 Correct 398 ms 73408 KB Output is correct
30 Correct 344 ms 73992 KB Output is correct
31 Correct 693 ms 82832 KB Output is correct
32 Correct 421 ms 76728 KB Output is correct
33 Correct 526 ms 74992 KB Output is correct
34 Correct 399 ms 71716 KB Output is correct
35 Correct 13 ms 23764 KB Output is correct
36 Correct 14 ms 23784 KB Output is correct
37 Correct 14 ms 23824 KB Output is correct
38 Correct 15 ms 23764 KB Output is correct
39 Correct 14 ms 23824 KB Output is correct
40 Correct 14 ms 23820 KB Output is correct
41 Correct 12 ms 23820 KB Output is correct
42 Correct 13 ms 23764 KB Output is correct
43 Correct 12 ms 23772 KB Output is correct
44 Correct 14 ms 23764 KB Output is correct
45 Correct 13 ms 23764 KB Output is correct
46 Correct 12 ms 23820 KB Output is correct
47 Correct 15 ms 23796 KB Output is correct
48 Correct 15 ms 23848 KB Output is correct
49 Correct 12 ms 23836 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 643 ms 78028 KB Output is correct
3 Correct 626 ms 78984 KB Output is correct
4 Correct 531 ms 81112 KB Output is correct
5 Correct 585 ms 71752 KB Output is correct
6 Correct 391 ms 71924 KB Output is correct
7 Correct 376 ms 72004 KB Output is correct
8 Correct 308 ms 72424 KB Output is correct
9 Correct 622 ms 77752 KB Output is correct
10 Correct 601 ms 80196 KB Output is correct
11 Correct 525 ms 72208 KB Output is correct
12 Correct 483 ms 71424 KB Output is correct
13 Correct 340 ms 72384 KB Output is correct
14 Correct 379 ms 72796 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 14 ms 23740 KB Output is correct
17 Correct 11 ms 23824 KB Output is correct
18 Correct 12 ms 23764 KB Output is correct
19 Correct 12 ms 23744 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23824 KB Output is correct
2 Correct 624 ms 80540 KB Output is correct
3 Correct 571 ms 77200 KB Output is correct
4 Correct 530 ms 81152 KB Output is correct
5 Correct 479 ms 73416 KB Output is correct
6 Correct 436 ms 73444 KB Output is correct
7 Correct 421 ms 73428 KB Output is correct
8 Correct 364 ms 73852 KB Output is correct
9 Correct 634 ms 82608 KB Output is correct
10 Correct 621 ms 77720 KB Output is correct
11 Correct 534 ms 75108 KB Output is correct
12 Correct 506 ms 71764 KB Output is correct
13 Correct 365 ms 72532 KB Output is correct
14 Correct 350 ms 72948 KB Output is correct
15 Correct 13 ms 23860 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23740 KB Output is correct
18 Correct 12 ms 23732 KB Output is correct
19 Correct 13 ms 23764 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23824 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 13 ms 24068 KB Output is correct
6 Correct 13 ms 24088 KB Output is correct
7 Correct 12 ms 24072 KB Output is correct
8 Correct 13 ms 24012 KB Output is correct
9 Correct 12 ms 23892 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 13 ms 23752 KB Output is correct
12 Correct 13 ms 23792 KB Output is correct
13 Correct 14 ms 23892 KB Output is correct
14 Correct 13 ms 23744 KB Output is correct
15 Correct 12 ms 23764 KB Output is correct
16 Correct 15 ms 23824 KB Output is correct
17 Correct 13 ms 23840 KB Output is correct
18 Correct 12 ms 23764 KB Output is correct
19 Correct 13 ms 23764 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 12 ms 23824 KB Output is correct
22 Correct 13 ms 23764 KB Output is correct
23 Correct 12 ms 23764 KB Output is correct
24 Correct 13 ms 23752 KB Output is correct
25 Correct 12 ms 23820 KB Output is correct
26 Correct 12 ms 23812 KB Output is correct
27 Correct 14 ms 23820 KB Output is correct
28 Correct 14 ms 23764 KB Output is correct
29 Correct 12 ms 23764 KB Output is correct
30 Correct 510 ms 75116 KB Output is correct
31 Correct 364 ms 71668 KB Output is correct
32 Correct 544 ms 78452 KB Output is correct
33 Correct 419 ms 73332 KB Output is correct
34 Correct 403 ms 73440 KB Output is correct
35 Correct 377 ms 73712 KB Output is correct
36 Correct 338 ms 73968 KB Output is correct
37 Correct 713 ms 80208 KB Output is correct
38 Correct 373 ms 77644 KB Output is correct
39 Correct 556 ms 75072 KB Output is correct
40 Correct 343 ms 71756 KB Output is correct
41 Correct 254 ms 72280 KB Output is correct
42 Correct 352 ms 72232 KB Output is correct
43 Correct 280 ms 72216 KB Output is correct
44 Correct 255 ms 72132 KB Output is correct
45 Correct 303 ms 72744 KB Output is correct
46 Correct 13 ms 23764 KB Output is correct
47 Correct 12 ms 23764 KB Output is correct
48 Correct 12 ms 23840 KB Output is correct
49 Correct 13 ms 23868 KB Output is correct
50 Correct 14 ms 23828 KB Output is correct
51 Correct 12 ms 23792 KB Output is correct
52 Correct 588 ms 75052 KB Output is correct
53 Correct 364 ms 71624 KB Output is correct
54 Correct 556 ms 81640 KB Output is correct
55 Correct 480 ms 73384 KB Output is correct
56 Correct 416 ms 73464 KB Output is correct
57 Correct 398 ms 73408 KB Output is correct
58 Correct 344 ms 73992 KB Output is correct
59 Correct 693 ms 82832 KB Output is correct
60 Correct 421 ms 76728 KB Output is correct
61 Correct 526 ms 74992 KB Output is correct
62 Correct 399 ms 71716 KB Output is correct
63 Correct 13 ms 23764 KB Output is correct
64 Correct 14 ms 23784 KB Output is correct
65 Correct 14 ms 23824 KB Output is correct
66 Correct 15 ms 23764 KB Output is correct
67 Correct 14 ms 23824 KB Output is correct
68 Correct 14 ms 23820 KB Output is correct
69 Correct 12 ms 23820 KB Output is correct
70 Correct 13 ms 23764 KB Output is correct
71 Correct 12 ms 23772 KB Output is correct
72 Correct 14 ms 23764 KB Output is correct
73 Correct 13 ms 23764 KB Output is correct
74 Correct 12 ms 23820 KB Output is correct
75 Correct 15 ms 23796 KB Output is correct
76 Correct 15 ms 23848 KB Output is correct
77 Correct 12 ms 23836 KB Output is correct
78 Correct 12 ms 23764 KB Output is correct
79 Correct 643 ms 78028 KB Output is correct
80 Correct 626 ms 78984 KB Output is correct
81 Correct 531 ms 81112 KB Output is correct
82 Correct 585 ms 71752 KB Output is correct
83 Correct 391 ms 71924 KB Output is correct
84 Correct 376 ms 72004 KB Output is correct
85 Correct 308 ms 72424 KB Output is correct
86 Correct 622 ms 77752 KB Output is correct
87 Correct 601 ms 80196 KB Output is correct
88 Correct 525 ms 72208 KB Output is correct
89 Correct 483 ms 71424 KB Output is correct
90 Correct 340 ms 72384 KB Output is correct
91 Correct 379 ms 72796 KB Output is correct
92 Correct 11 ms 23764 KB Output is correct
93 Correct 14 ms 23740 KB Output is correct
94 Correct 11 ms 23824 KB Output is correct
95 Correct 12 ms 23764 KB Output is correct
96 Correct 12 ms 23744 KB Output is correct
97 Correct 14 ms 23824 KB Output is correct
98 Correct 624 ms 80540 KB Output is correct
99 Correct 571 ms 77200 KB Output is correct
100 Correct 530 ms 81152 KB Output is correct
101 Correct 479 ms 73416 KB Output is correct
102 Correct 436 ms 73444 KB Output is correct
103 Correct 421 ms 73428 KB Output is correct
104 Correct 364 ms 73852 KB Output is correct
105 Correct 634 ms 82608 KB Output is correct
106 Correct 621 ms 77720 KB Output is correct
107 Correct 534 ms 75108 KB Output is correct
108 Correct 506 ms 71764 KB Output is correct
109 Correct 365 ms 72532 KB Output is correct
110 Correct 350 ms 72948 KB Output is correct
111 Correct 13 ms 23860 KB Output is correct
112 Correct 12 ms 23764 KB Output is correct
113 Correct 12 ms 23740 KB Output is correct
114 Correct 12 ms 23732 KB Output is correct
115 Correct 13 ms 23764 KB Output is correct
116 Correct 522 ms 73328 KB Output is correct
117 Correct 582 ms 71372 KB Output is correct
118 Correct 613 ms 81632 KB Output is correct
119 Correct 483 ms 73488 KB Output is correct
120 Correct 439 ms 73312 KB Output is correct
121 Correct 483 ms 73712 KB Output is correct
122 Correct 411 ms 74016 KB Output is correct
123 Correct 666 ms 80372 KB Output is correct
124 Correct 612 ms 76952 KB Output is correct
125 Correct 552 ms 74440 KB Output is correct
126 Correct 506 ms 71552 KB Output is correct
127 Correct 593 ms 71372 KB Output is correct
128 Correct 486 ms 72596 KB Output is correct
129 Correct 420 ms 72688 KB Output is correct