oj.uz

Submission #964299

# Submission time Handle Problem Language Result Execution time Memory
964299 2024-04-16T15:20:05 Z rolandpetrean Sprinkler (JOI22_sprinkler) C++17
9 / 100
 583 ms 97368 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;

const int N = 2e5 + 5;
vector<int> adj[N];
int par[N];

const int D = 42;
int h[N], wch[D][N];

void dfs(int u) {
  for (int v : adj[u]) {
    if (v == par[u]) continue;
    par[v] = u;
    dfs(v);
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n, l;
  cin >> n >> l;
  
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].pb(v);
    adj[v].pb(u);
  }
  for (int i = 0; i <= n; ++i) {
    for (int d = 0; d < D; ++d) wch[d][i] = 1;
  }
  
  dfs(1);
  
  for (int i = 1; i <= n; ++i) cin >> h[i];
  
  int q;
  cin >> q;
  
  while (q--) {
    int t;
    cin >> t;
    
    if (t == 1) {
      int u, d, w;
      cin >> u >> d >> w;
      
      auto mult = [&](int& var) {
        var = var * w % l;
      };
      
      int p = u;
      for (int i = 0; i <= d; ++i) {
        int descend = d - i;
        mult(wch[descend][p]);
        if (descend > 0) mult(wch[descend - 1][p]);
        p = par[u];
      }
    } else {
      int u;
      cin >> u;
      
      int p = u;
      int ans = h[u];
      for (int d = 0; d < D; ++d) {
        ans = ans * wch[d][p] % l;
        p = par[p];
      }
      cout << ans << endl;
    }
  }
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 61516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 57436 KB Output is correct
2 Correct 583 ms 93092 KB Output is correct
3 Correct 276 ms 93640 KB Output is correct
4 Correct 452 ms 95568 KB Output is correct
5 Correct 398 ms 93408 KB Output is correct
6 Correct 297 ms 92964 KB Output is correct
7 Correct 271 ms 93664 KB Output is correct
8 Correct 232 ms 93812 KB Output is correct
9 Correct 581 ms 97244 KB Output is correct
10 Correct 312 ms 97368 KB Output is correct
11 Correct 507 ms 92988 KB Output is correct
12 Correct 269 ms 93364 KB Output is correct
13 Correct 197 ms 93484 KB Output is correct
14 Correct 213 ms 94032 KB Output is correct
15 Correct 205 ms 93404 KB Output is correct
16 Correct 241 ms 93812 KB Output is correct
17 Correct 211 ms 94472 KB Output is correct
18 Correct 8 ms 51292 KB Output is correct
19 Correct 7 ms 51288 KB Output is correct
20 Correct 7 ms 51292 KB Output is correct
21 Correct 8 ms 51292 KB Output is correct
22 Correct 8 ms 51288 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 57436 KB Output is correct
2 Correct 583 ms 93092 KB Output is correct
3 Correct 276 ms 93640 KB Output is correct
4 Correct 452 ms 95568 KB Output is correct
5 Correct 398 ms 93408 KB Output is correct
6 Correct 297 ms 92964 KB Output is correct
7 Correct 271 ms 93664 KB Output is correct
8 Correct 232 ms 93812 KB Output is correct
9 Correct 581 ms 97244 KB Output is correct
10 Correct 312 ms 97368 KB Output is correct
11 Correct 507 ms 92988 KB Output is correct
12 Correct 269 ms 93364 KB Output is correct
13 Correct 197 ms 93484 KB Output is correct
14 Correct 213 ms 94032 KB Output is correct
15 Correct 205 ms 93404 KB Output is correct
16 Correct 241 ms 93812 KB Output is correct
17 Correct 211 ms 94472 KB Output is correct
18 Correct 8 ms 51292 KB Output is correct
19 Correct 7 ms 51288 KB Output is correct
20 Correct 7 ms 51292 KB Output is correct
21 Correct 8 ms 51292 KB Output is correct
22 Correct 8 ms 51288 KB Output is correct
23 Correct 7 ms 51292 KB Output is correct
24 Incorrect 509 ms 92884 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 51292 KB Output is correct
2 Incorrect 564 ms 94528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 51292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 61516 KB Output isn't correct
2 Halted 0 ms 0 KB -