oj.uz

Submission #785538

# Submission time Handle Problem Language Result Execution time Memory
785538 2023-07-17T10:05:55 Z kebine Sprinkler (JOI22_sprinkler) C++17
15 / 100
 289 ms 17228 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second

vector<int> adj[200005];
ll a[200005], cnt[200005], l;

void dfs1(int p, int x, int c, ll val) {
    a[x] = (a[x] * val) % l;
    if (c == 0) return;
    for (auto u : adj[x]) {
        if (u == p) continue;
        dfs1(x, u, c - 1, val);
    }
}

void dfs2(int x, int c) {
    a[x] = 0, cnt[x] = c;
    if (c == 1) return;
    for (auto u : adj[x]) {
        if (c - 1 > cnt[u]) dfs2(u, c - 1);
    }
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n;
    cin >> n >> l;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> a[i];
    int query;
    cin >> query;
    if (n <= 2000 and query <= 2000) {
        while (query--) {
            int type;
            cin >> type;
            if (type == 1) {
                int x, d;
                ll w;
                cin >> x >> d >> w;
                dfs1(0, x, d, w);
            }
            else {
                int x;
                cin >> x;
                cout << a[x] << "\n";
            }
        }
    }
    else {
        while (query--) {
            int type;
            cin >> type;
            if (type == 1) {
                int x, d;
                ll w;
                cin >> x >> d >> w;
                if (d + 1 > cnt[x]) dfs2(x, d + 1);
            }
            else {
                int x;
                cin >> x;
                cout << a[x] << "\n";
            }
        }
    }
}  
/*
4 7
1 2
2 3
3 4
1
1
1
1
3
1 2 1 2
1 1 0 2
2 1
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 4968 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 8 ms 5076 KB Output is correct
7 Correct 9 ms 5036 KB Output is correct
8 Correct 7 ms 5076 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 4 ms 5012 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5020 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4976 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 2 ms 4948 KB Output is correct
24 Correct 2 ms 4948 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 2 ms 4948 KB Output is correct
27 Correct 2 ms 4948 KB Output is correct
28 Correct 2 ms 4948 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 147 ms 17228 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 4948 KB Output is correct
2 Incorrect 147 ms 17228 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 4992 KB Output is correct
2 Correct 258 ms 15424 KB Output is correct
3 Correct 279 ms 14572 KB Output is correct
4 Correct 237 ms 15016 KB Output is correct
5 Correct 237 ms 15004 KB Output is correct
6 Correct 266 ms 15224 KB Output is correct
7 Correct 236 ms 15392 KB Output is correct
8 Correct 144 ms 15760 KB Output is correct
9 Correct 249 ms 15532 KB Output is correct
10 Correct 254 ms 14684 KB Output is correct
11 Correct 246 ms 15452 KB Output is correct
12 Correct 289 ms 14780 KB Output is correct
13 Correct 189 ms 15692 KB Output is correct
14 Correct 201 ms 16088 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Incorrect 226 ms 15304 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 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 4 ms 4968 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 8 ms 5076 KB Output is correct
7 Correct 9 ms 5036 KB Output is correct
8 Correct 7 ms 5076 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 4 ms 5012 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 3 ms 5020 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4976 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 2 ms 4948 KB Output is correct
24 Correct 2 ms 4948 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 2 ms 4948 KB Output is correct
27 Correct 2 ms 4948 KB Output is correct
28 Correct 2 ms 4948 KB Output is correct
29 Correct 2 ms 4948 KB Output is correct
30 Incorrect 147 ms 17228 KB Output isn't correct
31 Halted 0 ms 0 KB -