oj.uz

Submission #1003683

# Submission time Handle Problem Language Result Execution time Memory
1003683 2024-06-20T15:18:32 Z onbert Sprinkler (JOI22_sprinkler) C++17
41 / 100
 4000 ms 107648 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5, maxN = 8e5 + 5, m = 43;
int n, M;
vector<int> adj[maxn];
int newid[maxn], d[maxn], fa[maxn], a[maxn];
bool vis[maxn];

pair<int,int> range[maxn][m];
void dfs(int u) {
    range[u][0] = {newid[u], newid[u]};
    if (adj[u].size() == 0) return;
    for (int v:adj[u]) dfs(v);
    int sz = adj[u].size();
    int l = 0, r = sz - 1;
    for (int i=1;i<m;i++) {
        while (l < sz && range[adj[u][l]][i-1].first==-1) l++;
        while (r >= 0 && range[adj[u][r]][i-1].first==-1) r--;
        if (l>r) break;
        range[u][i] = {range[adj[u][l]][i-1].first, range[adj[u][r]][i-1].second};
    }
}

ll seg[maxN];
void build(int id, int l, int r) {
    seg[id] = 1;
    if (l==r) {
        seg[id] = a[l];
        return;
    }
    int mid = (l+r)>>1;
    build(id<<1, l, mid); build((id<<1)+1, mid+1, r);
}
void update(int id, int l, int r, int findl, int findr, int val) {
    if (r<findl || findr<l) return;
    if (findl<=l && r<=findr) {
        seg[id] = seg[id] * val % M;
        return;
    }
    int mid = (l+r)>>1;
    update((id<<1), l, mid, findl, findr, val);
    update((id<<1)+1, mid+1, r, findl, findr, val);
}
ll qry(int id, int l, int r, int target) {
    if (r<target || target<l) return 1;
    if (l==r) return seg[id];
    int mid = (l+r)>>1;
    return (seg[id] * qry(id<<1, l, mid, target) % M) * qry((id<<1)+1, mid+1, r, target) % M;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> M;
    for (int i=1;i<=n-1;i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int A[n+1];
    for (int i=1;i<=n;i++) cin >> A[i];
    queue<int> Q;
    Q.push(1);
    vis[1] = true, d[1] = 0, fa[1] = -1;
    int cnter = 0;
    while (Q.size() > 0) {
        int u = Q.front();
        cnter++;
        newid[u] = cnter;
        for (int v:adj[u]) if (!vis[v]) {
            vis[v] = true, fa[v] = u, d[v] = d[u] + 1;
            adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
            Q.push(v);
        }
        Q.pop();
    }
    for (int i=1;i<=n;i++) for (int j=0;j<m;j++) range[i][j] = {-1, -1};
    dfs(1);
    for (int i=1;i<=n;i++) a[newid[i]] = A[i];
    build(1, 1, n);
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t==1) {
            int x, D, w;
            cin >> x >> D >> w;
            int v = x;
            for (int dep = d[x]+D; dep>=d[x]-D && dep >= 0; dep--) {
                if (fa[v]!=-1 && dep-d[v] + d[x]-d[v] + 2 <= D) v = fa[v];
                update(1, 1, n, range[v][dep-d[v]].first, range[v][dep-d[v]].second, w);
            }
        } else if (t==2) {
            int x;
            cin >> x;
            cout << qry(1, 1, n, newid[x]) << '\n';
        }
        // for (int i=1;i<=n;i++) cout << qry(1, 1, n, newid[i]) << " "; cout << endl;
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 3 ms 5468 KB Output is correct
6 Correct 3 ms 5468 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 4972 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 2 ms 5016 KB Output is correct
19 Correct 2 ms 5212 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 2 ms 4956 KB Output is correct
22 Correct 2 ms 4956 KB Output is correct
23 Correct 2 ms 5212 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 2 ms 5044 KB Output is correct
26 Correct 2 ms 5212 KB Output is correct
27 Correct 2 ms 5212 KB Output is correct
28 Correct 3 ms 4968 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 325 ms 98644 KB Output is correct
3 Correct 416 ms 99340 KB Output is correct
4 Correct 426 ms 104892 KB Output is correct
5 Correct 347 ms 99156 KB Output is correct
6 Correct 362 ms 98644 KB Output is correct
7 Correct 307 ms 99408 KB Output is correct
8 Correct 273 ms 100560 KB Output is correct
9 Correct 361 ms 107648 KB Output is correct
10 Correct 495 ms 107348 KB Output is correct
11 Correct 300 ms 98644 KB Output is correct
12 Correct 398 ms 99136 KB Output is correct
13 Correct 282 ms 100296 KB Output is correct
14 Correct 266 ms 100292 KB Output is correct
15 Correct 268 ms 99540 KB Output is correct
16 Correct 283 ms 100176 KB Output is correct
17 Correct 326 ms 100628 KB Output is correct
18 Correct 2 ms 5208 KB Output is correct
19 Correct 2 ms 5212 KB Output is correct
20 Correct 2 ms 5212 KB Output is correct
21 Correct 2 ms 5212 KB Output is correct
22 Correct 3 ms 5212 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 325 ms 98644 KB Output is correct
3 Correct 416 ms 99340 KB Output is correct
4 Correct 426 ms 104892 KB Output is correct
5 Correct 347 ms 99156 KB Output is correct
6 Correct 362 ms 98644 KB Output is correct
7 Correct 307 ms 99408 KB Output is correct
8 Correct 273 ms 100560 KB Output is correct
9 Correct 361 ms 107648 KB Output is correct
10 Correct 495 ms 107348 KB Output is correct
11 Correct 300 ms 98644 KB Output is correct
12 Correct 398 ms 99136 KB Output is correct
13 Correct 282 ms 100296 KB Output is correct
14 Correct 266 ms 100292 KB Output is correct
15 Correct 268 ms 99540 KB Output is correct
16 Correct 283 ms 100176 KB Output is correct
17 Correct 326 ms 100628 KB Output is correct
18 Correct 2 ms 5208 KB Output is correct
19 Correct 2 ms 5212 KB Output is correct
20 Correct 2 ms 5212 KB Output is correct
21 Correct 2 ms 5212 KB Output is correct
22 Correct 3 ms 5212 KB Output is correct
23 Correct 2 ms 4952 KB Output is correct
24 Correct 330 ms 98792 KB Output is correct
25 Correct 488 ms 99136 KB Output is correct
26 Correct 426 ms 107472 KB Output is correct
27 Correct 363 ms 99032 KB Output is correct
28 Correct 391 ms 99156 KB Output is correct
29 Correct 301 ms 89168 KB Output is correct
30 Correct 252 ms 98500 KB Output is correct
31 Correct 355 ms 103976 KB Output is correct
32 Correct 566 ms 105044 KB Output is correct
33 Correct 295 ms 93520 KB Output is correct
34 Correct 476 ms 87688 KB Output is correct
35 Correct 2 ms 4956 KB Output is correct
36 Correct 2 ms 4956 KB Output is correct
37 Correct 2 ms 5212 KB Output is correct
38 Correct 2 ms 5212 KB Output is correct
39 Correct 2 ms 5152 KB Output is correct
40 Correct 2 ms 4956 KB Output is correct
41 Correct 2 ms 5000 KB Output is correct
42 Correct 2 ms 4956 KB Output is correct
43 Correct 2 ms 4956 KB Output is correct
44 Correct 2 ms 4956 KB Output is correct
45 Correct 2 ms 4952 KB Output is correct
46 Correct 2 ms 5004 KB Output is correct
47 Correct 3 ms 5212 KB Output is correct
48 Correct 2 ms 5212 KB Output is correct
49 Correct 3 ms 5212 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 829 ms 96812 KB Output is correct
3 Execution timed out 4017 ms 102480 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 861 ms 100576 KB Output is correct
3 Execution timed out 4048 ms 97792 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 3 ms 5468 KB Output is correct
6 Correct 3 ms 5468 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5212 KB Output is correct
12 Correct 2 ms 4972 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 2 ms 5212 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 2 ms 5016 KB Output is correct
19 Correct 2 ms 5212 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 2 ms 4956 KB Output is correct
22 Correct 2 ms 4956 KB Output is correct
23 Correct 2 ms 5212 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 2 ms 5044 KB Output is correct
26 Correct 2 ms 5212 KB Output is correct
27 Correct 2 ms 5212 KB Output is correct
28 Correct 3 ms 4968 KB Output is correct
29 Correct 2 ms 4956 KB Output is correct
30 Correct 325 ms 98644 KB Output is correct
31 Correct 416 ms 99340 KB Output is correct
32 Correct 426 ms 104892 KB Output is correct
33 Correct 347 ms 99156 KB Output is correct
34 Correct 362 ms 98644 KB Output is correct
35 Correct 307 ms 99408 KB Output is correct
36 Correct 273 ms 100560 KB Output is correct
37 Correct 361 ms 107648 KB Output is correct
38 Correct 495 ms 107348 KB Output is correct
39 Correct 300 ms 98644 KB Output is correct
40 Correct 398 ms 99136 KB Output is correct
41 Correct 282 ms 100296 KB Output is correct
42 Correct 266 ms 100292 KB Output is correct
43 Correct 268 ms 99540 KB Output is correct
44 Correct 283 ms 100176 KB Output is correct
45 Correct 326 ms 100628 KB Output is correct
46 Correct 2 ms 5208 KB Output is correct
47 Correct 2 ms 5212 KB Output is correct
48 Correct 2 ms 5212 KB Output is correct
49 Correct 2 ms 5212 KB Output is correct
50 Correct 3 ms 5212 KB Output is correct
51 Correct 2 ms 4952 KB Output is correct
52 Correct 330 ms 98792 KB Output is correct
53 Correct 488 ms 99136 KB Output is correct
54 Correct 426 ms 107472 KB Output is correct
55 Correct 363 ms 99032 KB Output is correct
56 Correct 391 ms 99156 KB Output is correct
57 Correct 301 ms 89168 KB Output is correct
58 Correct 252 ms 98500 KB Output is correct
59 Correct 355 ms 103976 KB Output is correct
60 Correct 566 ms 105044 KB Output is correct
61 Correct 295 ms 93520 KB Output is correct
62 Correct 476 ms 87688 KB Output is correct
63 Correct 2 ms 4956 KB Output is correct
64 Correct 2 ms 4956 KB Output is correct
65 Correct 2 ms 5212 KB Output is correct
66 Correct 2 ms 5212 KB Output is correct
67 Correct 2 ms 5152 KB Output is correct
68 Correct 2 ms 4956 KB Output is correct
69 Correct 2 ms 5000 KB Output is correct
70 Correct 2 ms 4956 KB Output is correct
71 Correct 2 ms 4956 KB Output is correct
72 Correct 2 ms 4956 KB Output is correct
73 Correct 2 ms 4952 KB Output is correct
74 Correct 2 ms 5004 KB Output is correct
75 Correct 3 ms 5212 KB Output is correct
76 Correct 2 ms 5212 KB Output is correct
77 Correct 3 ms 5212 KB Output is correct
78 Correct 2 ms 4956 KB Output is correct
79 Correct 829 ms 96812 KB Output is correct
80 Execution timed out 4017 ms 102480 KB Time limit exceeded
81 Halted 0 ms 0 KB -