結果

問題 No.30 たこやき工場
コンテスト
ユーザー codershifth
提出日時 2015-07-21 23:46:06
言語 C++11（廃止可能性あり）
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,972 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,712 ms
コンパイル使用メモリ 170,928 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-21 05:20:00
合計ジャッジ時間 2,428 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


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;
            // 木を逆にたどればよい
            // dfs + 遅延評価
            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];
            }
            // N 以外のノードで入ってくる辺の数が 0 のものは取り除く
            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<bool> vis(N,false);
            vector<vector<ll>>   dp(N,vector<ll>(N,-1));
            // x を 1 個作るのに必要な y の個数を返す
            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();
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new TakoyakiFactory();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0