제출 #964120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964120		LucaLucaM	Sprinkler (JOI22_sprinkler)	C++17	21 / 100	2912 ms	58804 KiB

sprinkler

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 9 / 9
• Subtask 3: 0 / 29
• Subtask 4: 12 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17