結果
問題 | No.2360 Path to Integer |
ユーザー |
![]() |
提出日時 | 2024-08-11 20:27:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 181 ms / 2,500 ms |
コード長 | 4,969 bytes |
コンパイル時間 | 5,547 ms |
コンパイル使用メモリ | 324,548 KB |
実行使用メモリ | 57,600 KB |
最終ジャッジ日時 | 2024-08-11 20:27:56 |
合計ジャッジ時間 | 8,203 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;#ifdef DEBUG#include "debug/all.hpp"#else#define debug(...) 42#endifusing ll = long long;using ull = unsigned long long;using ld = long double;using P = pair<ll, ll>;using tp = tuple<ll, ll, ll>;template <class T>using vec = vector<T>;template <class T>using vvec = vector<vec<T>>;#define all(hoge) (hoge).begin(), (hoge).end()#define en '\n'#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)#define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i)#define REP(i, n) rep(i, 0, n)#define REP2(i, n) rep2(i, 0, n)constexpr long long INF = 1LL << 60;constexpr int INF_INT = 1 << 30;// constexpr long long MOD = (ll)1e9 + 7;constexpr long long MOD = 998244353LL;static const ld pi = 3.141592653589793L;template <class T>inline bool chmin(T &a, T b) {if(a > b) {a = b;return true;}return false;}template <class T>inline bool chmax(T &a, T b) {if(a < b) {a = b;return true;}return false;}struct Edge {int to, rev;ll cap;Edge(int _to, int _rev, ll _cap) : to(_to), rev(_rev), cap(_cap) {}};typedef vector<Edge> Edges;typedef vector<Edges> Graph;void add_edge(Graph &G, int from, int to, ll cap, bool revFlag, ll revCap) {G[from].push_back(Edge(to, (int)G[to].size(), cap));if(revFlag)G[to].push_back(Edge(from, (int)G[from].size() - 1, revCap));}template <typename E, typename F, typename PE, typename PV>class RerootingDP {private:int n;E id;F merge;PE put_edge;PV put_vertex;Graph g;vector<E> subdp;vector<E> dp;public:vector<E> ans;RerootingDP(Graph _g, E _id, F f, PE pe, PV pv, int root = 0) : n(_g.size()), g(_g), id(_id), merge(f), put_edge(pe), put_vertex(pv), subdp(n,_id), dp(n, _id), ans(n, _id) {build(root);reroot(root);}void build(int root) {auto dfs = [&](auto &&self, int v, int p) -> void {E val = id;for(auto e : g[v]) {if(e.to == p)continue;self(self, e.to, v);E nval = put_edge(subdp[e.to], e);val = merge(val, nval);}subdp[v] = put_vertex(val, v);};dfs(dfs, root, -1);}void reroot(int root) {auto dfs = [&](auto &&self, int v, int p, E pval) -> void {vec<E> as;for(auto e : g[v]) {if(e.to == p) {as.push_back(put_edge(pval, e));} else {as.push_back(put_edge(subdp[e.to], e));}}vec<E> al(as.size(), as[0]);REP(i, as.size() - 1) {al[i + 1] = merge(as[i + 1], al[i]);}vec<E> ar(as.size(), as.back());REP2(i, as.size() - 1) {ar[i] = merge(as[i], ar[i + 1]);}dp[v] = merge(dp[v], put_vertex(al.back(), v));ans[v] = dp[v];int k = 0;for(auto e : g[v]) {if(e.to == p) {k++;continue;}E val = id;if(k - 1 >= 0)val = merge(val, al[k - 1]);if(k + 1 < ar.size())val = merge(val, ar[k + 1]);val = put_vertex(val, v);self(self, e.to, v, val);k++;}};dfs(dfs, root, -1, id);}};void solve() {ll n;cin >> n;vec<string> a(n);REP(i, n) { cin >> a[i]; }Graph g(n);REP(i, n - 1) {int u, v;cin >> u >> v;u--;v--;add_edge(g, u, v, 1, true, 1);}using mint = modint998244353;struct S {mint sum;mint con;S(mint _sum, mint _con) : sum(_sum), con(_con) {}S() : sum(0), con(0) {}};S id = S();auto merge = [](S a, S b) -> S { return S(a.sum + b.sum, a.con + b.con); };auto put_edge = [](S val, Edge e) { return val; };auto put_vertex = [&](S val, int v) {// cout << v << ":" << val.sum.val() << " " << val.con.val() << en;mint con = val.con + 1;mint sum = val.sum * mint(10).pow(a[v].size()) + con * stoll(a[v]);// cout << sum.val() << " " << con.val() << en;return S(sum, con);};RerootingDP rdp(g, id, merge, put_edge, put_vertex);auto dp = rdp.ans;mint ans = 0;for(auto i : dp) {ans += i.sum;}cout << ans.val() << en;}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);// cout << fixed << setprecision(10);// ll t;// cin >> t;// REP(i, t - 1) {// solve();// }solve();return 0;}