結果
問題 | No.30 たこやき工場 |
ユーザー |
![]() |
提出日時 | 2023-06-01 23:50:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 1,936 bytes |
コンパイル時間 | 1,365 ms |
コンパイル使用メモリ | 129,044 KB |
最終ジャッジ日時 | 2025-02-13 17:23:36 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <functional> #include <cmath> #include <string> #include <queue> #include <map> #include <bitset> #include <set> #include <stack> #include <numeric> #include <unordered_map> #include <random> using namespace std; using ll = long long; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vb = vector<bool>; using vvb = vector<vb>; using vd = vector<double>; using vs = vector<string>; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<double, double>; using vpii = vector<pii>; using vpll = vector<pll>; using vpdd = vector<pdd>; const int inf = (1 << 30) - 1; const ll INF = 1LL << 60; //const int MOD = 1000000007; const int MOD = 998244353; struct Edge { int to; ll cost; }; using Graph = vector<vector<Edge>>; vl memo; ll dfs(int s, Graph& g) { if (memo[s]) return memo[s]; ll ret = 0; for (auto& v : g[s]) { ll x = dfs(v.to, g); ret += x * v.cost; } return memo[s] = ret; } int main() { int n, m; cin >> n >> m; vi p(m), q(m), r(m); for (int i = 0; i < m; i++) { cin >> p[i] >> q[i] >> r[i]; } vl ans(n + 1, 0); Graph g(n + 1); // 辺を逆向きにして製品を作るのに必要な材料の数をDFSで求める方法はTLE // 大元の材料が次の材料に使われる数をメモ化再帰で求める for (int i = 0; i < m; i++) { g[p[i]].push_back({ r[i], q[i] }); } // 頂点の入次数を求める vi indeg(n + 1, 0); for (int i = 0; i < m; i++) { indeg[r[i]]++; } // memo[i]: 材料iが必要な数を保存 // 頂点N = 1 から逆向きに決まる memo.assign(n + 1, 0); memo[n] = 1; // 入次数 0 の頂点からDFSする for (int i = 1; i < n; i++) { if (indeg[i] == 0) dfs(i, g); } for (int i = 1; i < n; i++) { if (indeg[i] == 0) cout << memo[i] << endl; else cout << 0 << endl; } return 0; }