oj.uz

Submission #964120

# Submission time Handle Problem Language Result Execution time Memory
964120 2024-04-16T10:46:00 Z LucaLucaM Sprinkler (JOI22_sprinkler) C++17
21 / 100
 2912 ms 58804 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <queue>
#warning That's not AS, that's my AS

typedef long long ll;

const int NMAX = 2e5;
const int DMAX = 40;

int L;

int mult[NMAX + 1][DMAX + 1];

std::vector<int> g[NMAX + 1];
int parent[NMAX + 1];
int Time[NMAX + 1];
int timer;

void bfs() {
  std::queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    Time[u] = ++timer;
    std::vector<int> newG;
    for (const auto &v : g[u]) {
      if (!Time[v]) {
        parent[v] = u;
        newG.push_back(v);
        q.push(v);
      }
    }
    g[u] = newG;
  }
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);

  int n;
  std::cin >> n >> L;

  for (int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  bfs();

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= DMAX; j++) {
      mult[i][j] = 1;
    }
  }

  for (int i = 1; i <= n; i++) {
    int h;
    std::cin >> h;
    mult[i][0] = h;
  }

  int q;
  std::cin >> q;

  while (q--) {
    int type;
    std::cin >> type;
    if (type == 1) {
      int u, d, h;
      std::cin >> u >> d >> h;
      std::vector<std::pair<int, int>> ancestors;
      int v = u;
      for (int i = 0; i <= d && v != 0; i++) {
        ancestors.push_back({v, d - i});
        v = parent[v];
      }
      std::reverse(ancestors.begin(), ancestors.end());
      int maxDepth = -1;
      for (const auto &[v, depth] : ancestors) {
        /// i + depth > maxDepth => i > maxDepth - depth
        /// i + d - depth <= d <=> i <= depth
        for (int i = std::max(0, maxDepth - depth + 1); i <= depth; i++) {
          mult[v][i] = (ll) mult[v][i] * h % L;
        }
      }
    } else {
      int u;
      std::cin >> u;
      std::vector<std::pair<int, int>> ancestors;
      int v = u;
      int answer = 1;
      for (int i = 0; i <= DMAX && v != 0; i++) {
        answer = (ll) answer * mult[v][i] % L;
        v = parent[v];
      }
      std::cout << answer << '\n';
    }
  }

  return 0;
}

Compilation message

sprinkler.cpp:7:2: warning: #warning That's not AS, that's my AS [-Wcpp]
    7 | #warning That's not AS, that's my AS
      |  ^~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 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 2 ms 6488 KB Output is correct
2 Correct 453 ms 56952 KB Output is correct
3 Correct 306 ms 57324 KB Output is correct
4 Correct 401 ms 56916 KB Output is correct
5 Correct 339 ms 57300 KB Output is correct
6 Correct 286 ms 56824 KB Output is correct
7 Correct 256 ms 57432 KB Output is correct
8 Correct 203 ms 58804 KB Output is correct
9 Correct 470 ms 56428 KB Output is correct
10 Correct 281 ms 57216 KB Output is correct
11 Correct 409 ms 56856 KB Output is correct
12 Correct 285 ms 57176 KB Output is correct
13 Correct 184 ms 58624 KB Output is correct
14 Correct 204 ms 58356 KB Output is correct
15 Correct 193 ms 57960 KB Output is correct
16 Correct 208 ms 58072 KB Output is correct
17 Correct 203 ms 58704 KB Output is correct
18 Correct 2 ms 6488 KB Output is correct
19 Correct 2 ms 6492 KB Output is correct
20 Correct 2 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 453 ms 56952 KB Output is correct
3 Correct 306 ms 57324 KB Output is correct
4 Correct 401 ms 56916 KB Output is correct
5 Correct 339 ms 57300 KB Output is correct
6 Correct 286 ms 56824 KB Output is correct
7 Correct 256 ms 57432 KB Output is correct
8 Correct 203 ms 58804 KB Output is correct
9 Correct 470 ms 56428 KB Output is correct
10 Correct 281 ms 57216 KB Output is correct
11 Correct 409 ms 56856 KB Output is correct
12 Correct 285 ms 57176 KB Output is correct
13 Correct 184 ms 58624 KB Output is correct
14 Correct 204 ms 58356 KB Output is correct
15 Correct 193 ms 57960 KB Output is correct
16 Correct 208 ms 58072 KB Output is correct
17 Correct 203 ms 58704 KB Output is correct
18 Correct 2 ms 6488 KB Output is correct
19 Correct 2 ms 6492 KB Output is correct
20 Correct 2 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Incorrect 418 ms 56732 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 757 ms 53744 KB Output is correct
3 Correct 2779 ms 54448 KB Output is correct
4 Correct 1051 ms 53880 KB Output is correct
5 Correct 824 ms 53992 KB Output is correct
6 Correct 598 ms 54404 KB Output is correct
7 Correct 458 ms 54704 KB Output is correct
8 Correct 275 ms 56000 KB Output is correct
9 Correct 870 ms 53784 KB Output is correct
10 Correct 2912 ms 54204 KB Output is correct
11 Correct 627 ms 53764 KB Output is correct
12 Correct 2073 ms 54588 KB Output is correct
13 Correct 1747 ms 55424 KB Output is correct
14 Correct 1795 ms 56104 KB Output is correct
15 Correct 2 ms 6488 KB Output is correct
16 Correct 2 ms 6492 KB Output is correct
17 Correct 2 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 2 ms 6748 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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