No.30 たこやき工場 - yukicoder
- TLE するかなーと思ってたら案の定 TLE した問題。予測してるなら対応せんと。
- いまいち累積をメモ化する方法が思いつかず、頂点への入力辺が全て辿られてから次の頂点へ移動する。みたいな遅延評価でやってみた。N 以外のノードで入ってくる辺の数が 0 のものは取り除くをしないとWAになってしまったけど。
- solve_memo の方が解説にあった手法。次同じような問題をとくときはこっちのような実装をしよう。y を固定してやるのがミソなのだと思った。
class TakoyakiFactory {
public:
struct Edge {
Edge(int t, ll c) : to(t), cost(c) {}
int to;
ll cost;
};
void solve_dfs(void) {
int N,M;
cin>>N>>M;
vector<vector<Edge>> tree(N);
vector<int> ins(N,0);
REP(i,M)
{
int p,q,r;
cin>>p>>q>>r;
--p;
--r;
tree[r].emplace_back(p,q);
++ins[p];
}
REP(i, N-1)
{
if (ins[i] > 0)
continue;
for (auto e : tree[i])
--ins[e.to];
}
vector<ll> sum(N,0);
vector<ll> cache(N,0);
vector<int> vis(N,0);
function<void(int,ll)> dfs = [&](int x, ll n) {
++vis[x];
cache[x] += n;
if (vis[x] < ins[x])
return;
if (tree[x].empty())
{
sum[x] = cache[x];
return;
}
for (auto e : tree[x])
dfs(e.to, cache[x]*e.cost);
};
dfs(N-1,1);
REP(i,N-1)
cout<<sum[i]<<endl;
}
void solve_memo() {
int N,M;
cin>>N>>M;
vector<vector<Edge>> tree(N);
REP(i,M)
{
int p,q,r;
cin>>p>>q>>r;
--p;
--r;
tree[r].emplace_back(p,q);
}
vector<vector<ll>> dp(N,vector<ll>(N,-1));
function<ll(int,int)> dfs = [&](int x, int y) {
ll res = 0;
if (dp[x][y] >= 0)
return dp[x][y];
if (tree[x].empty())
return (x==y)? 1LL : 0LL;
for (auto e : tree[x])
res += (dfs(e.to, y) * e.cost);
return dp[x][y] = res;
};
REP(i,N-1)
cout<<dfs(N-1,i)<<endl;
}
void solve() {
solve_memo();
}
};