結果
問題 | No.2342 Triple Tree Query (Hard) |
ユーザー | SSRS |
提出日時 | 2023-05-30 16:37:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,953 bytes |
コンパイル時間 | 2,299 ms |
コンパイル使用メモリ | 180,576 KB |
実行使用メモリ | 26,088 KB |
最終ジャッジ日時 | 2024-12-28 12:30:58 |
合計ジャッジ時間 | 346,462 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
20,004 KB |
testcase_01 | AC | 3 ms
10,624 KB |
testcase_02 | AC | 39 ms
20,072 KB |
testcase_03 | AC | 49 ms
20,076 KB |
testcase_04 | AC | 31 ms
20,204 KB |
testcase_05 | AC | 36 ms
20,192 KB |
testcase_06 | AC | 43 ms
20,060 KB |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | TLE | - |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | TLE | - |
testcase_32 | TLE | - |
testcase_33 | TLE | - |
testcase_34 | TLE | - |
testcase_35 | TLE | - |
testcase_36 | TLE | - |
testcase_37 | TLE | - |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long MOD = 998244353;int main(){int N, Q;cin >> N >> Q;vector<vector<int>> E(N);for (int i = 0; i < N - 1; i++){int A, B;cin >> A >> B;A--;B--;E[A].push_back(B);E[B].push_back(A);}vector<long long> X(N);for (int i = 0; i < N; i++){cin >> X[i];}vector<int> p(N, -1);vector<vector<int>> c(N);vector<int> d(N, 0);queue<int> q;q.push(0);while (!q.empty()){int v = q.front();q.pop();for (int w : E[v]){if (w != p[v]){p[w] = v;c[v].push_back(w);d[w] = d[v] + 1;q.push(w);}}}for (int i = 0; i < Q; i++){int T;cin >> T;if (T == 1){int V;cin >> V;V--;cout << X[V] << endl;}if (T == 2){int V, K;long long C, D;cin >> V >> K >> C >> D;V--;vector<int> d2(N, -1);d2[V] = 0;queue<int> q;q.push(V);while (!q.empty()){int v = q.front();q.pop();for (int w : E[v]){if (d2[w] == -1){d2[w] = d2[v] + 1;q.push(w);}}}for (int j = 0; j < N; j++){if (d2[j] <= K){X[j] = (X[j] * C + D) % MOD;}}}if (T == 3){int V;long long C, D;cin >> V >> C >> D;V--;auto dfs = [&](auto dfs, int v) -> void {X[v] = (X[v] * C + D) % MOD;for (int w : c[v]){dfs(dfs, w);}};dfs(dfs, V);}if (T == 4){int U, V;long long C, D;cin >> U >> V >> C >> D;U--;V--;while (true){if (U == V){X[U] = (X[U] * C + D) % MOD;break;}if (d[U] > d[V]){swap(U, V);}X[V] = (X[V] * C + D) % MOD;V = p[V];}}}}