oj.uz

Submission #1004590

# Submission time Handle Problem Language Result Execution time Memory
1004590 2024-06-21T10:11:34 Z onbert Sprinkler (JOI22_sprinkler) C++17
12 / 100
 878 ms 57808 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 d[maxn], fa[maxn];
bool vis[maxn];

void dfs(int u) {
    vis[u] = true;
    if (adj[u].size() == 0) return;
    for (int v:adj[u]) if (!vis[v]){
        d[v] = d[u] + 1, fa[v] = u;
        dfs(v);
    }
}

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);
    }
    queue<int> Q;
    Q.push(1);
    fa[1] = -1, d[1] = 0;
    dfs(1);
    int val[n+1][m];
    for (int i=1;i<=n;i++) for (int j=0;j<m;j++) val[i][j] = 1;
    for (int i=1;i<=n;i++) cin >> val[i][0];
    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];
                val[v][dep - d[v]] = val[v][dep - d[v]] * w % M;
            }
        } else if (t==2) {
            int x;
            cin >> x;
            int ans = 1;
            for (int v = x; v != -1 && d[v] > d[x] - m; v = fa[v]) {
                ans = ans * val[v][d[x] - d[v]] % M;
            }
            cout << ans << endl;
        }
    }
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Incorrect 3 ms 5212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 795 ms 50408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 795 ms 50408 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 805 ms 47536 KB Output is correct
3 Correct 609 ms 56228 KB Output is correct
4 Correct 565 ms 55704 KB Output is correct
5 Correct 571 ms 55968 KB Output is correct
6 Correct 368 ms 55928 KB Output is correct
7 Correct 414 ms 56168 KB Output is correct
8 Correct 404 ms 56552 KB Output is correct
9 Correct 779 ms 55616 KB Output is correct
10 Correct 677 ms 56144 KB Output is correct
11 Correct 698 ms 55740 KB Output is correct
12 Correct 447 ms 56404 KB Output is correct
13 Correct 267 ms 57172 KB Output is correct
14 Correct 307 ms 57808 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 4 ms 4956 KB Output is correct
19 Correct 2 ms 6744 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Incorrect 878 ms 50388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Incorrect 3 ms 5212 KB Output isn't correct
5 Halted 0 ms 0 KB -