結果
問題 | No.2360 Path to Integer |
ユーザー |
|
提出日時 | 2023-06-24 19:32:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 210 ms / 2,500 ms |
コード長 | 1,564 bytes |
コンパイル時間 | 2,183 ms |
コンパイル使用メモリ | 206,328 KB |
最終ジャッジ日時 | 2025-02-15 02:08:21 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using Vl = vector<ll>;using Vi = vector<int>;using VVi = vector<Vi>;ll m = 998244353;int main () {int N;cin >> N;std::vector<string> S(N);for (auto& a : S) cin >> a;Vi tpr, par(N, -1);VVi gr(N);for (int i = 1; i < N; i ++) {int a, b;cin >> a >> b;gr[--a].push_back(--b);gr[b].push_back(a);}queue<int> que;que.push(0);while (!que.empty()) {int u = que.front();que.pop();tpr.push_back(u);for (auto v : gr[u]) {if (v == par[u]) continue;par[v] = u;que.push(v);}}for (int i = 0; i < N / 2; i ++) swap(tpr[i], tpr[N - i - 1]);// return 0;Vl dp(N), dp2(N), nm(N);// return 0;for (auto i : tpr) {// cout << i << endl;dp[i] = 0;nm[i] = 1;for (auto v : gr[i]) {if (v == par[i]) continue;dp[i] = (dp[i] + dp[v]) % m;nm[i] += nm[v];}for (int j = 0; j < S[i].size(); j ++) dp[i] = (dp[i] * 10) % m;ll ps = stoll(S[i]) % m;ps = (ps * nm[i]) % m;dp[i] = (dp[i] + ps) % m;}// return 0;dp2[0] = dp[0];for (int i = N - 2; i >= 0; i --) {int u = tpr[i];int p = par[u];ll x = dp[u];for (int j = 0; j < S[p].size(); j ++) x = (x * 10) % m;x = (x + nm[u] * stoll(S[p])) % m;dp2[u] = (dp2[p] + m - x) % m;for (int j = 0; j < S[u].size(); j ++) dp2[u] = (dp2[u] * 10) % m;dp2[u] = (dp2[u] + (N - nm[u]) * stoll(S[u])) % m;dp2[u] = (dp2[u] + dp[u]) % m;}// return 0;ll ans = 0;for (auto a : dp2) ans = (ans + a) % m;cout << ans << endl;}