結果
問題 | No.30 たこやき工場 |
ユーザー |
![]() |
提出日時 | 2021-10-21 13:16:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 755 bytes |
コンパイル時間 | 4,645 ms |
コンパイル使用メモリ | 256,256 KB |
最終ジャッジ日時 | 2025-01-25 02:15:58 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 100000001 int main(){ int n,m; cin>>n>>m; vector<int> p(m),q(m),r(m); scc_graph S(n); vector<vector<int>> E(n); rep(i,m){ cin>>p[i]>>q[i]>>r[i]; p[i]--; r[i]--; E[r[i]].push_back(i); S.add_edge(r[i],p[i]); } auto s = S.scc(); vector<long long> dp(n,0); rep(i,n){ int ind = s[i][0]; if(ind==n-1)dp[ind] = 1LL; bool f = false; rep(j,E[ind].size()){ int to = p[E[ind][j]]; long long c = q[E[ind][j]]; dp[to] += dp[ind] * c; f = true; } if(f)dp[ind] = 0; } rep(i,n-1)cout<<dp[i]<<endl; return 0; }