Submission #674605

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
674605	2022-12-25 10:28:21	someone	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	861 ms	99536 KiB

sprinkler

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M = 2e5 + 42, N = 2 * M, T = 19, INF = 1e18 + 42, MOD = 1e9 + 7;
vector<int> adj[M];
int n, l, q, id = 0, h[M], pere[M], prof[M], ch[M][42];
void dfs(int i, int pre, int depth = 0) {
    pere[i] = pre;
    prof[i] = depth;
    for(int j : adj[i])
        if(j != pre)
            dfs(j, i, depth+1);
}
void update(int i, int d, int prod) {
    do {
        if(i == 0 || d < 2) {
            for(int j = 0; j <= d; j++)
                ch[i][j] = ch[i][j] * prod % l;
        } else {
            ch[i][d] = ch[i][d] * prod % l;
            ch[i][d-1] = ch[i][d-1] * prod % l;
        }
        d--;
        i = pere[i];
    } while(i != -1 && d >= 0);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17